## 10537 - The Toll! Revisited

Moderator: Board moderators

windows2k
Experienced poster
Posts: 136
Joined: Sat Apr 05, 2003 3:29 pm
Location: Taiwan

### 10537 - The Toll! Revisited

Why I always get Time Limit Exceed
It only 52 nodes in a graph,and I uses shortest path to solve it.
if n=0, what output we should do ?

cyfra
Experienced poster
Posts: 144
Joined: Thu Nov 22, 2001 2:00 am
Location: Gdynia, Poland
Hi!

Hmm.. your method is good. I also did it with Dijkstra for finding the shortest pathes... (and got AC in less then 1sec)

But I think that there are 2 things that can cause TLE...

1.) Check how long your function for visiting cities works. ( the function, that counts the minimal number of cash you need to have before entering the city, so that you can leave it with known amount of cash)

2.) Don't forget that the final answer can be greater than 2^31 ...

Good Luck inkfish
New poster
Posts: 7
Joined: Wed Jul 30, 2003 9:04 am
Help!
[cpp]

#include <stdio.h>

// A-Z: 0-25
// a-z: 30-55
long long maxvalue;
long long cost;
long long v;

int parent;
int isin;
int scr,tar;

int convert_1(char ch)
{
if(ch>='a' && ch<='z') return (ch-'a'+30);
return (ch-'A');
}

char convert_2(int x)
{
if(x<30) return (char)('A'+x);
return (char)('a'+x-30);
}

long long pre(long long x,int id)
{
long long k,b;

if(id<30){
k=x/19;
b=x%19;
if(b) return 20*k+b+1; return 20*k;
}else return x+1;
}

void dp()
{
long long temp;
long long minv;
int minid;
int i;

for(i=0;i<60;i++){
cost=maxvalue; parent=-1; isin=0;
}

cost[tar]=v;
isin[tar]=1;
for(i=0;i<60;i++){
temp=pre(v,tar);
if(temp<cost){
cost=temp;
parent=tar;
}
}
}

while(1){
minv=maxvalue;
minid=-1;
for(i=0;i<60;i++)
if(!isin && cost<minv){
minv=cost;
minid=i;
}
if(minid==-1) break; /* I got WA, and if i delete this ,it will be TLE ,*/
isin[minid]=1;
for(i=0;i<60;i++){
temp=pre(cost[minid],minid);
if(temp<cost[i]){
cost[i]=temp;
parent[i]=minid;
}else{
if(temp==cost[i] && parent[i]>minid) parent[i]=minid;
}
}
}
if(minid==scr) break;
}
}

void print(int cases)
{
int temp;

printf("Case %d:\n",cases);
printf("%lld\n",cost[scr]);
printf("%c",convert_2(scr));
temp=scr;
while(1){
temp=parent[temp];
printf("-%c",convert_2(temp));
if(temp==tar) break;
}
printf("\n");
}

int main()
{
char str;
long long n;
int cases=0;
char ch1,ch2;
int i,j;
int v1,v2;
// freopen("test.txt","r",stdin);
while(1){
scanf("%lld",&n);
if(n==-1) break;
cases++;

maxvalue=10000000;
maxvalue*=10000000;
for(i=0;i<60;i++)
for(i=0;i<n;i++){
scanf("%s",str);
ch1=str;
scanf("%s",str);
ch2=str;
v1=convert_1(ch1);
v2=convert_1(ch2);
}
scanf("%lld",&v);
scanf("%s",str);
ch1=str;
scanf("%s",str);
ch2=str;
scr=convert_1(ch1);
tar=convert_1(ch2);

dp();
print(cases);
}
return 0;
}
[/cpp]

inkfish
New poster
Posts: 7
Joined: Wed Jul 30, 2003 9:04 am
I get Ac now
my last program was wrong when there is just one node.

ne0
New poster
Posts: 2
Joined: Fri Aug 01, 2003 12:17 am
Contact:
Dear all,

I think, I've read all the notes and every thing seems okay, but i still get WA :(
I would be thankful :)

here is my code:
[cpp]
#include<iostream>
#include<string.h>

#define INFINITE 2E14
#define int long long
#define CEIL(x) ((x)==(int)(x)?(x):(int)(x)+1)
#define MIN(x,y) ((x)<(y)?(x):(y))
#define CODE(x) ((x)<='Z'?(x)-'A':(x)-'a'+26)
#define DECODE(x) ((char)(x<26?x+'A':x-26+'a'))
#define INC(x,c) ((c)<26?CEIL((x)*20/19.0):(x)+1)
#define DEC(x,c) ((c)<26?(x)-CEIL(x/20.0):(x)-1)

using namespace std;

int src,tgt,m;
int graph;
int dist;
int mark;

void dijkstra()
{
for(int i=0;i<52;i++)
mark=0,dist=INFINITE;

dist[tgt]=m;
for(;;)
{
int mindex=-1;
for(int i=0;i<52;i++)
if(!mark&&(mindex==-1||dist<dist[mindex]))
mindex=i;
if(mindex==-1||dist[mindex]>=INFINITE||mindex==src)
break;
mark[mindex]=1;
for(int i=0;i<52;i++)
if(!mark&&graph[mindex])
dist=MIN(dist,INC(dist[mindex],mindex));
}
}

main()
{
int N=0;
while(cin>>m,m+1)
{
memset(graph,0,sizeof graph);
char c1,c2;
while(m--)
{
cin>>c1>>c2;
graph[CODE(c1)][CODE(c2)]=1;
}
cin>>m>>c1>>c2;
src=CODE(c1);tgt=CODE(c2);
if(m)
dijkstra();
else
cout<<"Case "<<++N<<":"<<endl;

cout<<dist[src]<<endl;
cout<<DECODE(src);
do
{
int i;
for(i=0;i<52;i++)
if(graph[src]&&dist==DEC(dist[src],i))
break;
if(i==52)
break;
src=i;
cout<<'-'<<((char)DECODE(src));
}while(src!=tgt);
cout<<endl;
}
return 0;
}
[/cpp]

ne0
New poster
Posts: 2
Joined: Fri Aug 01, 2003 12:17 am
Contact:

### sorry

sorry, in the main function:
[cpp]
src=CODE(c1);tgt=CODE(c2);
if(m)
dijkstra();
else
cout<<"Case "<<++N<<":"<<endl
[/cpp]
must be:
[cpp]
src=CODE(c1);tgt=CODE(c2);
dijkstra();
cout<<"Case "<<++N<<":"<<endl;
[/cpp]

but it's still WA

UFP2161
A great helper
Posts: 277
Joined: Mon Jul 21, 2003 7:49 pm
Contact:

### 10537 - Toll! Revisited - I/O

Could someone post some input/outputs for this? Thanks in advance!

Faizur
New poster
Posts: 39
Joined: Fri Jun 06, 2003 3:04 pm
how can i solve this kind of problems?? using single source shortest path algo..can anyone explain a bit.

UFP2161
A great helper
Posts: 277
Joined: Mon Jul 21, 2003 7:49 pm
Contact:
You can use single source shortest path. It's just not "normal", since you don't have any fixed weights, so you're recreating them backwards as you leave a town/village until you hit your starting destination.

Anyways, I pretty much verified that my number of items that I must start with is correct (checked it with some code I found online, assuming it's right too). Which probably also means my path is correct. So, I don't know anymore.

Regardless of what the description says, are there things like p = 0? or there isn't a connection between starting and destination cities?

I just don't know what other border cases to try!

Faizur
New poster
Posts: 39
Joined: Fri Jun 06, 2003 3:04 pm
Where can i find thes codes pls.

carneiro
Learning poster
Posts: 54
Joined: Sun May 18, 2003 1:19 am
Location: Rio de Janeiro, Brazil
Contact:
How does the input with n = 0 looks like ?

Code: Select all

``````0
23 A A``````
or something else ?

And what's the expected output for that ?

my (WA) program outputs this :

Code: Select all

``````Case 1:
23
A``````
[]s
Mauricio Oliveira Carneiro

miras
Learning poster
Posts: 98
Joined: Sat Jun 14, 2003 1:45 pm
it schould be

Case 1:
23
A-A little joey
Guru
Posts: 1080
Joined: Thu Dec 19, 2002 7:37 pm
Well, that isn't funny at all!

The problem statement clearly says:
Actually, the path contains all the city/village names that Sindbad sees along his journey. Two consecutive city/village names in the path are separated by a hyphen.
In the example you give, Sindbad sees only one city, so the path length should be one and the correct output should be:

Case 1:
23
A

The path A-A would implicate that Sindbad leaves the town, changes his mind and reenters again, in which case he should pay toll, and the correct answer would be:

Case 1:
25
A-A

There would be no consecutive towns inbetween which to place a hyphen if he doesn't leave and reenter.

Still got WA any which way, so there must be something else I missed...

Per
A great helper
Posts: 429
Joined: Fri Nov 29, 2002 11:27 pm
Location: Sweden
To clear up the confusion:
My AC program answers "A" as the path for such a test case (which I definitely agree is the correct interpretation), so if miras is AC with his/hers interpretation, there can't be any such test cases.

These test cases are proably too easy, but anyway:

Code: Select all

``````4
A b
A B
b c
B c
18 A c
4
A b
A B
b c
B c
19 A c``````
Output:

Code: Select all

``````Case 1:
20
A-B-c
Case 2:
21
A-b-c``````

shahriar_manzoor