10099 - The Tourist Guide

[Observer]

No... You've misinterpreted the qq......

In the sample input,
the tourist guide "wants to take 99 tourists from city 1 to city 7"

If he takes the route 1-2-4-7, Max. no. of people per trip
= Min(30, 25, 35) = 25

Thus max. no. of tourists per trip = 25 - 1 = 24 (Why? )

In 5 trips, max no. of tourists taken from 1 to 7
= 24 * 5 = 120 >= 99

So the sample input/output is correct!

[junior]

Thanks a lot Mr.

I do appreciate that

[junior]

I've done the algorithm but why did I get Compile Error for 12 times???

I've followed the ANSI procedure like

int main(){
...
..
...
return 0;
}
etc.

and I've compiled it in my home with both Borland C and gcc
(in GNU/LINUX) and it was succesfull

but why I still got CE???

any comments or suggestions???

[Dominik Michniewski]

please post error messages or code - it'll be easier to tell you what's wrong

Best regards
DM

[junior]

Never Mind ,
I just forgot , I used the //comment

Thanks anyway

[raymond85]

I have no idae why i am getting WA. I have test the program with many different test cases. Please Help! Here's my code:

Code: Select all

Just figured out I misunderstand the input format......

[de]

I don't know why got WA.

Thanks for you help..><

[cpp]#include <iostream.h>

long max(long a,long b)
{
if (a>b)
return a;
else
return b;
}

long min(long a,long b)
{
if (a<b)
return a;
else
return b;
}

int main()
{
int n,r;
long graph[120][120];
int k,t,t2;
int x,y,l;
int s,d,p;
long temp;
long sum;
int count;

count=0;

while (cin >> n >> r)
{
if (n==0 && r==0)
break;

count++;

for (t=0 ;t<=n ;t++)
{
for (t2=0 ;t2<=n ;t2++)
graph[t][t2]=0;
}

for (t=0 ;t<r ;t++)
{
cin >> x >> y >> l;
graph[x][y]=graph[y][x]=l;
}

cin >> s >> d >> p;

for (k=1 ;k<=n ;k++)
{
for (t=1 ;t<=n ;t++)
{
for (t2=1 ;t2<=n ;t2++)
{
if (graph[t][k]==0 || graph[k][t2]==0)
continue;

temp=min(graph[t][k],graph[k][t2]);

graph[t][t2]=max(graph[t][t2],temp);
}
}
}

temp=graph[s][d];

temp--;

sum=p/temp;

if (temp%p!=0)
sum++;

cout << "Scenario #" << count << endl;
cout << "Minimum Number of Trips = " << sum << endl << endl;
}
return 0;
}[/cpp]

[rakeb]

there are some errors in ur code


[cpp]
graph[x][y]=graph[y][x]=l;
[/cpp]
should be
[cpp]
graph[x][y]=graph[y][x]=l-1; //because the tourist will also go
[/cpp]

and u r doing

[cpp]
temp--
[/cpp]

this is wrong. u should not do this

u checked
[cpp]
if (temp%p!=0)
sum++;
[/cpp]

i think it should be

[cpp]
if (p%temp!=0)
sum++;
[/cpp]

hope this can help

[de]

special thanks for your help!!..^^

[dserrano]

Can I solve the problem 10099 using a variation of Dijkstra algorithm?
In each step, instead of looking for the lowest cost, I look for the highest minimum cost of the whole path.
I'm in the right way, or not ?

[Larry]

Probably, but I solved this using min-max Floyd's.

[maxagaze]

Dijkstra worked for me.

[watershed]

This problem is Floyd algorithm.
Why did I get WA?
Thanks for your help....

[cpp]nothing[/cpp]

[Eric3k]

You should set all the values of map to 0 for every test case and then read the input.

[backbencher]

can anyone clarify the sample i/o to me?

how the output is : 5 trips ???