## 10449 - Traffic

Moderator: Board moderators

Guru
Posts: 724
Joined: Wed Dec 19, 2001 2:00 am
Location: Germany

### 10449 - Traffic

What is the trick with this problem?
I tried to solve it by using Bellmann-Ford algorithm.
Since (busyness of destination - busyness of source)^3 can be <0 Dijkstra is not possible, and Floyd-Warshall fails on negative weight cycles as far as I know. Is there another algorithm to be used instead of Bellmann-Ford? And does anyone of those who got Accepted during online contest know a tricky testcase?

shahriar_manzoor
Posts: 399
Joined: Sat Jan 12, 2002 2:00 am

### I am sorry

"However, for the queries that gives less than 3 units of minimum total
> earning or if destination is not reachable, print a '?'. "

This should be the actual problem statement.

I guess the problemsetter's logic was if destination is not reachable you don't have to pay anything hence payed amount is zero hence less than 3. I will change the problem statement soon.

Guru
Posts: 724
Joined: Wed Dec 19, 2001 2:00 am
Location: Germany
Thanks, now I got Accepted. Anyway, there was also another mistake in my code.

Larry
Guru
Posts: 647
Joined: Wed Jun 26, 2002 10:12 pm
Location: Hong Kong and New York City
Contact:
Can you post some sample input? I don't know if my implementation is off or if I forgot something...

..
A great helper
Posts: 454
Joined: Thu Oct 18, 2001 2:00 am
Location: Hong Kong
I try to use Floyd-Warshal to solve this problem but got WA.

After running Floyd-Warshal, if there is a vertex v, such that w(v, v) is negative. Then I know v is on a negative cycle.
To check if the path from 1 to a can use the negative cycle to decrease the weight w(1, a). I check if there exist a path 1->v->a where v is a vertex on negative cycle. (It is easy to check after running Floyd-Warshal)

But I don't know why I got WA, confused....
My signature:
We can learn much more in discussion than reading source code.
• I HATE testing account.
• Don't send me source code for debug.

Alexander Grushetsky
New poster
Posts: 28
Joined: Wed Jul 31, 2002 10:33 am
Location: Ukraine
Contact:
During contest I used exactly the same method. But at first I forgot that if the number of destination point is 1 then answer always should be "?" (because cost of going from 1 to 1 is zero).

Guru
Posts: 724
Joined: Wed Dec 19, 2001 2:00 am
Location: Germany
Try this testcase:
6 1 4 5 7 9 10
6
1 2
2 3
3 4
4 5
5 6
6 4
6
4
2
1
5
6
3
Output:
Set #1
?
27
?
?
?
28

..
A great helper
Posts: 454
Joined: Thu Oct 18, 2001 2:00 am
Location: Hong Kong
Thanks Alexander!!!
I just think I can handle that input is 1, but actually I missed it!!
My signature:
We can learn much more in discussion than reading source code.
• I HATE testing account.
• Don't send me source code for debug.

Larry
Guru
Posts: 647
Joined: Wed Jun 26, 2002 10:12 pm
Location: Hong Kong and New York City
Contact:
Is there a faster way to do this than Floyd?

Dominik Michniewski
Guru
Posts: 834
Joined: Wed May 29, 2002 4:11 pm
Location: Wroclaw, Poland
Contact:
I passed test from sample input, passed test given by Adrian , but got WA in OJ. Could anyone help me with implementation of Bellman-Ford algorithm ?

I use following algorithm:

Code: Select all

``````#define MAXINT   0x7FFFFFFF /* maximal value for long int */

long int paths[MAX][MAX],lens[MAX];

void BellmanFord(int N,int s)
{
int i,u,v;

for(i=0;i<N;i++) lens[i] = MAXINT;
lens[s] = 0;
for(i=0;i<N-1;i++)
for(u=0;u<N;u++)
for(v=0;v<N;v++)
if(paths[u][v] < MAXINT)
if(lens[v] > lens[u] + paths[u][v]) lens[v] = lens[u] + paths[u][v];
for(v=0;v<N;v++)
if((lens[s] < MAXINT) && (paths[s][v] < MAXINT))
if(lens[v] > lens[s] + paths[s][v]) lens[v] = 0;
}
``````
I think, that I must have wrong implement this algorithm, but I don't know what I'm doing wrong ...

Regards
Dominik Michniewski
If you really want to get Accepted, try to think about possible, and after that - about impossible ... and you'll get, what you want ....
Born from ashes - restarting counter of problems (800+ solved problems)

dynamic
New poster
Posts: 5
Joined: Tue Aug 06, 2002 8:48 am
why this simple code get TLE?I just intend to read the input...

Code: Select all

``````#include <stdio.h>
#include <string.h>

int main()
{
int n,m,r;
int i,j,k;
while(scanf("%d",&n)!=EOF){
for(i=0;i<n;i++) scanf("%d",&k);
scanf("%d",&r);
for(i=0;i<r;i++) scanf("%d%d",&j,&k);
scanf("%d",&m);
for(i=0;i<m;i++) scanf("%d",&k);
}
return 0;
}
``````

dynamic
New poster
Posts: 5
Joined: Tue Aug 06, 2002 8:48 am
To Dominik Michniewski:your MAXINT is too big and will overflow when doing addition

Alexander Grushetsky
New poster
Posts: 28
Joined: Wed Jul 31, 2002 10:33 am
Location: Ukraine
Contact:
to dynamic:
change

Code: Select all

``while(scanf("%d",&n)!=EOF)``
to

Code: Select all

``while(scanf("%d",&n)==1)``
or use cin ( while(cin>>n) )
I don't know the source of this bug. I also had it when I rewrote my solution after contest.

dynamic
New poster
Posts: 5
Joined: Tue Aug 06, 2002 8:48 am
Thank you very much!

I think i know the reason,there must be some extra characters at the end of the input.as i keep reading integers,i will never reach EOF.that's too bad,i kept getting runtime error during the contest

Dominik Michniewski
Guru
Posts: 834
Joined: Wed May 29, 2002 4:11 pm
Location: Wroclaw, Poland
Contact:
I still got WA ....
I try to change value of MAXINT to 0x3FFFFFFF and if after addition in BellmanFord value is bigger set it back to MAXINT - but WA ....

I try to rewrite my code to use adjacent list instead of table, but get WA too (and I don't use MAXINT in that in time of computation... )

Could anyone tell me what's maybe wrong or give me some additional test cases ? I become right results for sample input and for Adrian tests ...

Regards
Dominik
If you really want to get Accepted, try to think about possible, and after that - about impossible ... and you'll get, what you want ....
Born from ashes - restarting counter of problems (800+ solved problems)