10449 - Traffic

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

Moderator: Board moderators

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

10449 - Traffic

Post by Adrian Kuegel » Tue Feb 11, 2003 2:15 pm

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
System administrator & Problemsetter
Posts: 399
Joined: Sat Jan 12, 2002 2:00 am

I am sorry

Post by shahriar_manzoor » Tue Feb 11, 2003 5:25 pm

"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
Guru
Posts: 724
Joined: Wed Dec 19, 2001 2:00 am
Location: Germany

Post by Adrian Kuegel » Tue Feb 11, 2003 6:21 pm

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:

Post by Larry » Tue Feb 11, 2003 6:35 pm

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

Post by .. » Tue Feb 11, 2003 6:59 pm

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

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

Post by Alexander Grushetsky » Tue Feb 11, 2003 7:37 pm

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
Guru
Posts: 724
Joined: Wed Dec 19, 2001 2:00 am
Location: Germany

Post by Adrian Kuegel » Tue Feb 11, 2003 7:59 pm

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

Post by .. » Tue Feb 11, 2003 8:43 pm

Thanks Alexander!!!
I just think I can handle that input is 1, but actually I missed it!!
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.

Larry
Guru
Posts: 647
Joined: Wed Jun 26, 2002 10:12 pm
Location: Hong Kong and New York City
Contact:

Post by Larry » Wed Feb 12, 2003 10:17 am

Is there a faster way to do this than Floyd?

Dominik Michniewski
Guru
Posts: 832
Joined: Wed May 29, 2002 4:11 pm
Location: Wroclaw, Poland
Contact:

Post by Dominik Michniewski » Wed Feb 12, 2003 3:12 pm

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

Post by dynamic » Wed Feb 12, 2003 7:09 pm

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
New poster
Posts: 5
Joined: Tue Aug 06, 2002 8:48 am

Post by dynamic » Wed Feb 12, 2003 7:14 pm

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:

Post by Alexander Grushetsky » Wed Feb 12, 2003 9:40 pm

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

Post by dynamic » Thu Feb 13, 2003 4:19 am

Thank you very much! :D

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

Dominik Michniewski
Guru
Posts: 832
Joined: Wed May 29, 2002 4:11 pm
Location: Wroclaw, Poland
Contact:

Post by Dominik Michniewski » Thu Feb 13, 2003 10:39 am

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)

Post Reply

Return to “Volume 104 (10400-10499)”