762 - We Ship Cheap

[nagary]

If there are multiple minumum length routes given a pair of source and destination cities, do I need to print out all minimum routes.

[titid_gede]

if there are more than one, any one is acceptable.
hope it helps and good luck!

[nagary]

WA -_-
Are there any suggested test cases ?

[Mahmud776]

The highest number of city would be 680 or less.For this you have to
maintain this. For your help, i gave some sample inputs.


Sample inputs:
9
JV PT
JV TA
JV DA
PT KA
KA HP
DA TA
DA HP
HP AP
AP TA
JV DA

9
JV PT
JV TA
JV DA
PT KA
KA HP
DA TA
DA HP
HP AP
AP TA
JV AP

9
JV PT
JV TA
JV DA
PT KA
KA HP
DA TA
DA HP
HP AP
AP TA
JV HP

8
JV PT
JV TA
PT KA
KA HP
DA TA
DA HP
HP AP
AP TA
JV HP

Output for this inputs:
JV DA

JV TA
TA AP

JV DA
DA HP

JV PT
PT KA
KA HP

[shamim]

This problem has a correction program, so individual results may vary.
Eventhough both could be correct.

[Riyad]

hey ,
can some one give me some test data for 762 . i am getting WA for this prob ..i assumed total node to be 1200 or less ....i used simple BFS for solving this ,, while i was getting WA i optted for FLoyd Warshall(All Pairs Shortest Path ) but to no avail, got TLE .............
so some one plizzzzzzzzz give me some input or i may post the code here ..............
Thanx In Advance
Riyad

[technobug]

By the way, there might be no route at all, or the city might even not exist!

[miras]

hey...
try with this test...

Code: Select all

2
AA BB
CC DD
GG HH

Output is

Code: Select all

no route

[miras]

hey...
try with this test...

Code: Select all

2
AA BB
CC DD
GG HH

Output is

Code: Select all

no route

[miras]

hey...
try with this test...

Code: Select all

2
AA BB
CC DD
GG HH

Output is

Code: Select all

no route

[miras]

hey...
try with this test...

Code: Select all

2
AA BB
CC DD
GG HH

Output is

Code: Select all

no route

[miras]

hey...
try with this test...

Code: Select all

2
AA BB
CC DD
GG HH

Output is

Code: Select all

no route

[lovemagic]

my code gets output limit exceeded! can anybody help?
//start
#include<stdio.h>
#include<string.h>
#define max 105
#define inf 99999

char city[max][35],first[35],sec[35],start[35],dest[35],faltu[10];
int matrix[max][max];

int mini(int a,int b){
if(a>b) return b;
else return a;
}

int maxi(int a,int b){
if(a>b) return a;
else return b;
}

void main(){
int road_seg,i,j,k,i1,i2,i3,min,len,flag,total_city,t,tmp;

while(gets(faltu)&& faltu[0]){
sscanf(faltu,"%d",&road_seg);
i1=1;
for(i=0;i<road_seg;i++){
scanf("%s %s",first,sec);
len=strlen(first);first[len]=NULL;
len=strlen(sec);sec[len]=NULL;
flag=0;
for(i2=0;i2<i1;i2++){
if(strcmp(city[i2],first)==0){
j=i2;
flag=1;
break;
}
}
if(flag==0){
strcpy(city[i1],first);
j=i1;i1++;
}
flag=0;
for(i2=0;i2<i1;i2++){
if(strcmp(city[i2],sec)==0){
k=i2;
flag=1;
break;
}
}
if(flag==0){
strcpy(city[i1],sec);
k=i1;i1++;
}
matrix[j][k]=matrix[k][j]=1;
}
total_city=i1-1;

for(i=1;i<=total_city;i++)
for(j=1;j<=total_city;j++)
if(matrix[j]!=1)
matrix[j]=inf;

for(k=1;k<=total_city;k++)
for(i=1;i<=total_city;i++)
for(j=1;j<=total_city;j++)
matrix[j]=matrix[j]=mini( matrix[j], (matrix[k]+matrix[k][j]) );

scanf("%s %s",start,dest);

flag=0;
for(i=1;i<=total_city;i++){
if(strcmp(city,start)==0){j=i;flag++;}
if(strcmp(city,dest)==0){k=i;flag++;}
if(flag==2)break;
}

for(i1=1;i1<=total_city;i1++)matrix[i1][i1]=0;

if(matrix[j][k]==9999)printf("No route\n");
else{
i1=j;i2=k;t=0;
while(1){
if(i1==i2)break;
printf("%s ",city[i1]);
tmp=matrix[i1][i2];min=9999;
for(i=1;i<=total_city;i++){
if(i!=i1){
if(matrix[i1]+matrix[i2]==tmp && matrix[i1][i]<min){
min=matrix[i1][i];
t=i;
}
}
}
printf("%s\n",city[t]);
i1=t;
}
}
printf("\n");
for(i=1;i<=total_city;i++)
for(j=1;j<=total_city;j++)
matrix[i][j]=0;
gets(faltu);
gets(faltu);
}
}

[james299]

I tried to solve this problem , after a lot of WA I got a very tricky input.

Try this :

Code: Select all

0
AA BB

output :

Code: Select all

No route

I didn't expect such input so my code won't get AC.
Just after I made a little change, AC now.

Hope it could help.

[tuman]

what should i do now???

my code gives all the output correct for the i\o given above. Is it possible to get wrong answer only for presentation related problem?