10537 - The Toll! Revisited

[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 ?

[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

[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]

[inkfish]

I get Ac now
my last program was wrong when there is just one node.

[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]

[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

[UFP2161]

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

[Faizur]

how can i solve this kind of problems?? using single source shortest path algo..can anyone explain a bit.

[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!

[Faizur]

Where can i find thes codes pls.

[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

[miras]

it schould be



Case 1:
23
A-A

[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...

[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

[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.