10449 - Traffic

[Adrian Kuegel]

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]

"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.

[Adrian Kuegel]

Thanks, now I got Accepted. Anyway, there was also another mistake in my code.

[Larry]

Can you post some sample input? I don't know if my implementation is off or if I forgot something...

[..]

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

[Alexander Grushetsky]

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).

[Adrian Kuegel]

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

[..]

Thanks Alexander!!!
I just think I can handle that input is 1, but actually I missed it!!

[Larry]

Is there a faster way to do this than Floyd?

[Dominik Michniewski]

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

[dynamic]

why this simple code get TLE?I just intend to read the input...
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;
}

[dynamic]

To Dominik Michniewski:your MAXINT is too big and will overflow when doing addition

[Alexander Grushetsky]

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]

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]

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