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 BellmannFord algorithm.
Since (busyness of destination  busyness of source)^3 can be <0 Dijkstra is not possible, and FloydWarshall fails on negative weight cycles as far as I know. Is there another algorithm to be used instead of BellmannFord? And does anyone of those who got Accepted during online contest know a tricky testcase?
I tried to solve it by using BellmannFord algorithm.
Since (busyness of destination  busyness of source)^3 can be <0 Dijkstra is not possible, and FloydWarshall fails on negative weight cycles as far as I know. Is there another algorithm to be used instead of BellmannFord? And does anyone of those who got Accepted during online contest know a tricky testcase?

 System administrator & Problemsetter
 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.
> 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
I try to use FloydWarshal to solve this problem but got WA.
After running FloydWarshal, 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 FloydWarshal)
But I don't know why I got WA, confused....
After running FloydWarshal, 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 FloydWarshal)
But I don't know why I got WA, confused....
My signature:
 Please make discussion about the algorithm BRFORE posting source code.
We can learn much more in discussion than reading source code.  I HATE testing account.
 Don't send me source code for debug.

 New poster
 Posts: 28
 Joined: Wed Jul 31, 2002 10:33 am
 Location: Ukraine
 Contact:

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

 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 BellmanFord algorithm ?
I use following algorithm:
I think, that I must have wrong implement this algorithm, but I don't know what I'm doing wrong ...
Regards
Dominik Michniewski
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<N1;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;
}
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)
Born from ashes  restarting counter of problems (800+ solved problems)
why this simple code get TLE?I just intend to read the input...
Please help me,thanks in advance
Please help me,thanks in advance
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;
}

 New poster
 Posts: 28
 Joined: Wed Jul 31, 2002 10:33 am
 Location: Ukraine
 Contact:
to dynamic:
change
to
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.
change
Code: Select all
while(scanf("%d",&n)!=EOF)
Code: Select all
while(scanf("%d",&n)==1)
I don't know the source of this bug. I also had it when I rewrote my solution after contest.

 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
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)
Born from ashes  restarting counter of problems (800+ solved problems)