762 - We Ship Cheap

All about problems in Volume 7. If there is a thread about your problem, please use it. If not, create one with its number in the subject.

Moderator: Board moderators

nagary
New poster
Posts: 4
Joined: Sun Jul 20, 2003 8:23 pm

762 - We Ship Cheap

Post by nagary » Wed Aug 13, 2003 10:15 am

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
Experienced poster
Posts: 187
Joined: Wed Dec 11, 2002 2:03 pm
Location: Mount Papandayan, Garut

Post by titid_gede » Wed Aug 13, 2003 11:04 am

if there are more than one, any one is acceptable.
hope it helps and good luck!
Kalo mau kaya, buat apa sekolah?

nagary
New poster
Posts: 4
Joined: Sun Jul 20, 2003 8:23 pm

762 WA

Post by nagary » Sun Aug 17, 2003 6:10 pm

WA -_-
Are there any suggested test cases ?

Mahmud776
New poster
Posts: 22
Joined: Mon Dec 22, 2003 9:29 am
Location: Canada

Sample inputs

Post by Mahmud776 » Mon Dec 29, 2003 10:00 am

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

User avatar
shamim
A great helper
Posts: 498
Joined: Mon Dec 30, 2002 10:10 am
Location: Bozeman, Montana, USA

Post by shamim » Mon Jan 05, 2004 1:45 pm

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

User avatar
Riyad
Experienced poster
Posts: 131
Joined: Thu Aug 14, 2003 10:23 pm
Location: BUET
Contact:

762,WA

Post by Riyad » Thu Mar 18, 2004 10:30 pm

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
HOLD ME NOW ,, I AM 6 FEET FROM THE EDGE AND I AM THINKIN.. MAY BE SIX FEET IS SO FAR DOWN

technobug
Learning poster
Posts: 88
Joined: Sat Nov 15, 2003 6:41 pm
Location: Brasilien
Contact:

Post by technobug » Mon Apr 05, 2004 5:21 am

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

miras
Learning poster
Posts: 98
Joined: Sat Jun 14, 2003 1:45 pm

Post by miras » Sun Aug 22, 2004 10:58 pm

hey...
try with this test...

Code: Select all

2
AA BB
CC DD
GG HH

Output is

Code: Select all

no route
Remember Never Give Up
Regrads
Miras

miras
Learning poster
Posts: 98
Joined: Sat Jun 14, 2003 1:45 pm

Post by miras » Sun Aug 22, 2004 10:59 pm

hey...
try with this test...

Code: Select all

2
AA BB
CC DD
GG HH

Output is

Code: Select all

no route
Remember Never Give Up
Regrads
Miras

miras
Learning poster
Posts: 98
Joined: Sat Jun 14, 2003 1:45 pm

Post by miras » Sun Aug 22, 2004 10:59 pm

hey...
try with this test...

Code: Select all

2
AA BB
CC DD
GG HH

Output is

Code: Select all

no route
Remember Never Give Up
Regrads
Miras

miras
Learning poster
Posts: 98
Joined: Sat Jun 14, 2003 1:45 pm

Post by miras » Sun Aug 22, 2004 10:59 pm

hey...
try with this test...

Code: Select all

2
AA BB
CC DD
GG HH

Output is

Code: Select all

no route
Remember Never Give Up
Regrads
Miras

miras
Learning poster
Posts: 98
Joined: Sat Jun 14, 2003 1:45 pm

Post by miras » Sun Aug 22, 2004 11:00 pm

hey...
try with this test...

Code: Select all

2
AA BB
CC DD
GG HH

Output is

Code: Select all

no route
Remember Never Give Up
Regrads
Miras

lovemagic
Learning poster
Posts: 52
Joined: Thu Oct 02, 2003 11:38 am

762-OLE

Post by lovemagic » Thu Sep 23, 2004 8:50 pm

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

james299
New poster
Posts: 10
Joined: Tue Jul 26, 2005 8:58 am
Location: Taiwan

annoying...

Post by james299 » Thu Aug 11, 2005 4:06 am

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.
:wink:

User avatar
tuman
New poster
Posts: 24
Joined: Sat Oct 22, 2005 7:30 pm
Location: CUET
Contact:

Post by tuman » Fri Mar 31, 2006 10:05 pm

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?

Post Reply

Return to “Volume 7 (700-799)”