1233 - USHER

[just_yousef]

hello every one,
im trying to solve this problem and it keeps giving RE.
Can you help me find out where the bug is??
And im i using the correct approach ??
Thank you

Code: Select all

AC :D 

[brianfry713]

You can solve it using the Floyd-Warshall algorithm.

[just_yousef]

You can solve it using the Floyd-Warshall algorithm.

I tried SPFA and Got AC, Thanks

[giusevtr]

Code: Select all

31
18 5
2 1 4
1 3 2
1 1 3
2 2 0 1 4
1 3 5
1 5 0
22 5
2 1 4
1 3 2
1 1 3
2 2 0 1 4
1 3 5
1 5 0 
24 5
2 1 4
1 3 2
1 1 3
2 2 0 1 4
1 3 5
1 5 0
14 3
1 1
2 7 2 2 3
1 2 0
1 3 2
7 3
1 1
2 7 2 2 3
1 2 0
1 3 2
8 3
1 1
2 7 2 2 3
1 2 0
1 3 2
20 3
1 1
2 7 2 2 3
1 2 0
1 3 2
19 3
1 1
2 7 2 2 3
1 2 0
1 3 2
5 2
1 1
1 5 2
0
5 2
1 1
1 4 2
0
5 2
1 1
1 5 2
1 3 0
10 1
1 1
1 2 0
9 1
1 1
1 2 0
8 1
1 1
1 2 0

5 1
1 1
1 6 0

10 1
1 1
1 8 0

10 3
2 1 2
1 8 0
1 2 3
1 2 2

21 7
2 1 4
1 2 2
1 5 3
2 2 1 4 0
1 2 5
1 2 4
0
0

22 7
2 1 4
1 2 2
1 5 3
2 2 1 4 0
1 2 5
1 2 4
0
0

1000000 1
1 1
1 2 0

8 2
2 1 2
2 4 0 2 2
2 4 0 2 1

100 5
1 1
0
1 2 3
1 2 2
0
0

11 8
2 1 8
1 2 2
1 3 3
3 7 0 2 4 3 5
2 10 2 2 5
1 5 6
3 3 7 6 0 9 3
1 2 0
1 2 7

11 10
3 1 8 9
1 2 2
1 3 3
3 7 0 2 4 3 5
2 10 2 2 5
1 5 6
3 3 7 6 0 9 3
1 2 0
1 2 7
1 2 10
1 2 0

16 10
3 1 8 9
1 2 2
1 3 3
3 7 0 2 4 3 5
2 10 2 2 5
1 5 6
3 3 7 6 0 9 3
1 4 0
1 4 7
1 4 10
1 4 0

100 1
1 1
1 99 0

100 1
1 1
1 100 0

100 9
2 1 2
1 99 0
1 2 3
1 2 4
1 2 5
1 2 6
1 2 7
1 2 8
1 2 9
1 2 0

500 3
1 1
1 2 2
1 2 3
1 2 2

20 7
2 1 4
1 2 2
1 2 3
1 2 1
1 2 5
0
3 2 7 2 0 2 2
1 2 6

8 2
1 1
2 2 2 5 2
1 2 0
0

AC output:

Code: Select all

3
4
4
2
0
1
3
2
0
0
0
8
7
6
0
1
1
1
2
999998
2
0
3
3
2
1
0
6
0
0
2

[anacharsis]

How can this possibly be done with Floyd Warshall?
That has a cubic big-O run time, so with up to 500 vertices, that could amount to 125,000,000 iterations for a single problem instance.