## 1233 - USHER

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

Moderator: Board moderators

just_yousef
New poster
Posts: 50
Joined: Tue Dec 17, 2013 11:01 pm

### 1233 - USHER

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
``````
Last edited by just_yousef on Sun Jul 20, 2014 3:26 am, edited 1 time in total.

brianfry713
Guru
Posts: 5947
Joined: Thu Sep 01, 2011 9:09 am
Location: San Jose, CA, USA

### Re: 1233 - USHER

You can solve it using the Floyd-Warshall algorithm.
Check input and AC output for thousands of problems on uDebug!

just_yousef
New poster
Posts: 50
Joined: Tue Dec 17, 2013 11:01 pm

### Re: 1233 - USHER

brianfry713 wrote:You can solve it using the Floyd-Warshall algorithm.
I tried SPFA and Got AC, Thanks

giusevtr
New poster
Posts: 2
Joined: Mon Nov 05, 2012 8:16 pm
Location: Miami

### Re: 1233 - USHER

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
Learning poster
Posts: 69
Joined: Mon Feb 09, 2015 1:56 am

### Re: 1233 - USHER

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.