first...you must know that there is only one test case, ans this test case contents lots of tests...

second...if you used the floyed to calculate the minimum circle，you must check the path you recorded.and, yes, the order of the crossing is not important.

ok,I WA on the recording of the path,because I ignored that floyed will change the mid node of my path...

sorry for my english...

there is one test case that may help you :


98 146
1 2 1
2 3 300
3 4 1
4 5 300
5 6 1
6 7 300
7 8 1
8 9 300
9 10 1
10 11 300
11 12 1
12 13 300
13 14 1
14 15 300
15 16 1
16 17 300
17 18 1
18 19 300
19 20 1
20 21 300
21 22 1
22 23 300
23 24 1
24 25 300
25 26 1
26 27 300
27 28 1
28 29 300
29 30 1
30 31 300
31 32 1
32 33 300
33 34 1
34 35 300
35 36 1
36 37 300
37 38 1
38 39 300
39 40 1
40 41 300
41 42 1
42 43 300
43 44 1
44 45 300
45 46 1
46 47 300
47 48 1
48 49 300
50 51 300
51 52 1
52 53 300
53 54 1
54 55 300
55 56 1
56 57 300
57 58 1
58 59 300
59 60 1
60 61 300
61 62 1
62 63 300
63 64 1
64 65 300
65 66 1
66 67 300
67 68 1
68 69 300
69 70 1
70 71 300
71 72 1
72 73 300
73 74 1
74 75 300
75 76 1
76 77 300
77 78 1
78 79 300
79 80 1
80 81 300
81 82 1
82 83 300
83 84 1
84 85 300
85 86 1
86 87 300
87 88 1
88 89 300
89 90 1
90 91 300
91 92 1
92 93 300
93 94 1
94 95 300
95 96 1
96 97 300
97 98 1
1 50 5
2 51 5
3 52 5
4 53 5
5 54 5
6 55 5
7 56 5
8 57 5
9 58 5
10 59 5
11 60 5
12 61 5
13 62 5
14 63 5
15 64 5
16 65 5
17 66 5
18 67 5
19 68 5
20 69 5
21 70 5
22 71 5
23 72 5
24 73 5
25 74 5
26 75 5
27 76 5
28 77 5
29 78 5
30 79 5
31 80 5
32 81 5
33 82 5
34 83 5
35 84 5
36 85 5
37 86 5
38 87 5
39 88 5
40 89 5
41 90 5
42 91 5
43 92 5
44 93 5
45 94 5
46 95 5
47 96 5
48 97 5
49 98 5
50 49 3


the answer is

49 50 1 2 51 52 3 4 53 54 5 6 55 56 7 8 57 58 9 10 59 60 11 12 61 62 13 14 63 64 15 16 65 66 17 18 67 68 19 20 69 70 21 22 71 72 23 24 73 74 25 26 75 76 27 28 77 78 29 30 79 80 31 32 81 82 33 34 83 84 35 36 85 86 37 38 87 88 39 40 89 90 41 42 91 92 43 44 93 94 45 46 95 96 47 48 97 98

Hello!
I pass your test data but I still get WA,why?
Is there any other  trick?

Sorry for my poor english too. :）

Oh,I get AC!
Beacuse my inf is too large.
It should be small than INT_MAX/3.

So somebody else who  get WA should notice it.

More test data:
5 0
6 1
1 2 3
-1

Edited by author 02.08.2011 08:24

Edited by author 02.08.2011 08:25

my answer is

1 2 51 52 3 4 53 54 5 6 55 56 7 8 57 58 9 10 59 60 11 12 61 62 13 14 63 64 15 16 65 66 17 18 67 68 19 20 69 70 21 22 71 72 23 24 73 74 25 26 75 76 27 28 77 78 29 30 79 80 31 32 81 82 33 34 83 84 35 36 85 86 37 38 87 88 39 40 89 90 41 42 91 92 43 44 93 94 45 46 95 96 47 48 97 98 49 50
but it is stall WA in test one! who can give more test cases?

6 9
1 2 1
2 3 100
3 4 1
4 5 100
5 6 1
6 1 100
1 4 5
2 5 5
3 6 5

1 2 5 6 3 4

Edited by author 20.04.2013 19:32

Thanks, you are true hero!