762 - We Ship Cheap
Moderator: Board moderators
762 - We Ship Cheap
If there are multiple minumum length routes given a pair of source and destination cities, do I need to print out all minimum routes.
-
- Experienced poster
- Posts: 187
- Joined: Wed Dec 11, 2002 2:03 pm
- Location: Mount Papandayan, Garut
Sample inputs
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
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
762,WA
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
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
HOLD ME NOW ,, I AM 6 FEET FROM THE EDGE AND I AM THINKIN.. MAY BE SIX FEET IS SO FAR DOWN
762-OLE
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);
}
}
//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);
}
}
khobaib
annoying...
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.
![:wink:](./images/smilies/icon_wink.gif)
![:(](./images/smilies/icon_frown.gif)
Try this :
Code: Select all
0
AA BB
Code: Select all
No route
Just after I made a little change, AC now.
Hope it could help.
![:wink:](./images/smilies/icon_wink.gif)