Page 1 of 2

10537 - The Toll! Revisited

Posted: Tue Jul 29, 2003 6:09 am
by windows2k
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 ?

Posted: Tue Jul 29, 2003 1:00 pm
by cyfra
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 ...

I hope it will help you

Good Luck :wink:

Posted: Wed Jul 30, 2003 9:13 am
by inkfish
Help!
[cpp]

#include <stdio.h>

// A-Z: 0-25
// a-z: 30-55
long long maxvalue;
bool link[60][60];
long long cost[60];
long long v;

int parent[60];
int isin[60];
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(link[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(link[i][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[10];
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(j=0;j<60;j++) link[i][j]=0;
for(i=0;i<n;i++){
scanf("%s",str);
ch1=str[0];
scanf("%s",str);
ch2=str[0];
v1=convert_1(ch1);
v2=convert_1(ch2);
link[v1][v2]=1;
link[v2][v1]=1;
}
scanf("%lld",&v);
scanf("%s",str);
ch1=str[0];
scanf("%s",str);
ch2=str[0];
scr=convert_1(ch1);
tar=convert_1(ch2);

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

Posted: Wed Jul 30, 2003 9:19 am
by inkfish
I get Ac now
my last program was wrong when there is just one node.

Posted: Fri Aug 01, 2003 12:36 am
by ne0
Dear all,

I think, I've read all the notes and every thing seems okay, but i still get WA :(
Can someone help me please?
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[52][52];
int dist[52];
int mark[52];

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]

sorry

Posted: Fri Aug 01, 2003 12:48 am
by ne0
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

10537 - Toll! Revisited - I/O

Posted: Thu Aug 14, 2003 2:04 am
by UFP2161
Could someone post some input/outputs for this? Thanks in advance!

Posted: Sun Aug 17, 2003 12:02 pm
by Faizur
how can i solve this kind of problems?? using single source shortest path algo..can anyone explain a bit.

Posted: Wed Aug 20, 2003 8:00 am
by UFP2161
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!

Posted: Wed Aug 20, 2003 1:13 pm
by Faizur
Where can i find thes codes pls.

Posted: Sun Aug 31, 2003 5:26 am
by carneiro
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

Posted: Mon Sep 01, 2003 1:35 pm
by miras
it schould be



Case 1:
23
A-A :lol:

Posted: Mon Sep 01, 2003 4:03 pm
by little joey
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...

Posted: Mon Sep 01, 2003 11:54 pm
by Per
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

hmm

Posted: Tue Sep 02, 2003 3:57 am
by shahriar_manzoor
The following output format is OK: (When source and dest are same)

Case 1:
23
A

and there are such cases in the judge data.