Page 1 of 1

### 1233 - USHER

Posted: Fri May 09, 2014 10:58 am
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
``````

### Re: 1233 - USHER

Posted: Fri May 09, 2014 8:26 pm
You can solve it using the Floyd-Warshall algorithm.

### Re: 1233 - USHER

Posted: Sun Jul 20, 2014 3:27 am
brianfry713 wrote:You can solve it using the Floyd-Warshall algorithm.
I tried SPFA and Got AC, Thanks

### Re: 1233 - USHER

Posted: Mon Oct 27, 2014 9:30 pm

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

### Re: 1233 - USHER

Posted: Sat May 28, 2016 10:25 pm
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.