OJ Board

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

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

WA -_-
Are there any suggested test cases ?

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

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

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

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

hey...
try with this test... Output is

hey...
try with this test... Output is

hey...
try with this test... Output is

hey...
try with this test... Output is

hey...
try with this test... Output is

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);
}
}

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

Try this : output : 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.

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?