1. Вы пишите:найти для экскурсии кратчайший маршрут, начинающийся и заканчивающийся в одном и том же месте, т.е. количество перекрестков в маршруте должно быть N+1?. в след. абзаце: Все числа x1, …, xk должны быть различны. т.е.  либо маршрут не должен заканчиваться на том же перекресте где начался либо должно быть дополнительное условие Х1=Хк. это принципиальная ошибка в условии.
2. пример который вы привели:
5 7
1 4 1
1 3 300
3 1 10
1 2 16
2 3 100
2 5 15
5 3 20
4 3
1 2 10
1 3 20
1 4 30
-1
дает результат:
1 3 5 2
No solution.
а куда вы в первом тесте дели перекрестов №4?
3. Исходя из примера маршрут не должен содержать в себе все перекрестки?

Ошибки очевидны. те решения, что вы приняли - частные, случайно полученные.
Уточняйте условия и проверяйте свое решение.

Edited by author 07.11.2014 13:33

Что-то я не совсем понял условие задачи.
"M двусторонних дорог" - т.е. вроде как не ор. граф.
Но пример и решение говорят, о том, что скорее это все таки ор. граф.

1 3 300
3 1 10

Так есть ориентация у ребер или нету?

6 6
1 2 1
1 3 1
2 3 10
4 5 2
4 6 2
6 5 2
-1

ANS:
4 5 6

My algorithm passes all the tests I have designed, but still misses test 1. Can I get the input for this test ?

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

My AC code:

input:
>   3 3
>   1 2 1
>   1 2 1
>   1 3 1
>   -1

output:
>   No solution.

Why not
>   1 2

There are two roads connecting "1" and "2", so the route could be 1 - 2 - 1, with different road 1 - 2 and 2 -1

What's should the following input get?

3 4
1 2 1
2 3 1
1 3 1
1 2 1

3 4
1 2 1
2 3 1
1 3 1
1 2 10

-1

Thanks!

Try this test:
6 6
1 2 1
2 3 100
3 1 99
4 5 150
5 6 1
6 4 1
-1

Answer: 4 5 6

!!Please be aware of fmt.Scanf poor performance!!

I did everything to test it on Timus and feel so sorry for it. My code logic is ok except this! It took a day to figure out.

I got AC with FreePascal before, and now Golang. So my advice is: read all input first using bufio and ioutil like this:

input = bufio.NewReader(os.Stdin)
output = bufio.NewWriter(os.Stdout)

_wholeText, _ := ioutil.ReadAll(input)
numbers := strings.Fields(string(_wholeText))

Idea is Dijkstra (N times from every node). I can proof that minimal cycle turns when we  add one edge in root tree (tree of distance).

Edited by author 06.09.2015 15:53

Edited by author 06.09.2015 15:54

I use the algo with N Dijkstras. Does anyone know, can I get AC with that algo, or 0.5 sec is not enough for it?

Hello.
Do not pass the test number two. Tested the algorithm all the data found on the Internet, all the tests pass. What is important is whether the value of the order of numbers in the answer? Whether equivalent variants "1 2 3 4" and "3 4 1 2"?
Perhaps you can give a piece of advice.

Условия:
> найти для экскурсии кратчайший маршрут, начинающийся и заканчивающийся в одном и том же месте.
> Ваша программа должна найти маршрут наименьшей длины
> и M двусторонних дорог,

В ТЗ не сказано что нужно обойти максимум перекрестков, не сказано что нельзя ехать назад.
А значит путь: 1 -> 4 -> 1 подходит.

I can not solve it,please tell me how to solve it,thank you!^_^

0.343 sec.
Just to let you know. ;)

I tested it offline,and I got WA 90.
But when I submited it.I got Crash(Access Violation).
There's another question.
For this input:
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
-1

My answer is:49 98 97
And I think it was quit correct.
But the output 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

Can anybody tell me how to solve these questions.

Thank you very much

I read this algorithm in INTRODUCTION OF ALGORITHM at chapter 25.If you had already read this algorithm,you can easily solve this problem.

Please add this test (if it is not already here and if it is not too hard):

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

repeated 5 times.

One of my AC submissions works 0.8 seconds locally on this test, but works 0.187 seconds
max on judge. Even though my computer is slower than judge, it still looks like a big
difference.

I implemented the first idea came to my mind: for each connected vertices v1,v2 removing edge v1-v2 and finding shortest paths from v1 to v2 with Dijkstra. As for my estimations it should be O(edges^2) or O(vertices^4) for very connected graphs.

It was reported in other threads of this discussion that this solution should fit time limits, but mine does not pass test #3 (time limit exceed).

I am curious if solutions like mine now can be accepted. Did anyone have success with that approach after rejudgement in Sep 2013? Or now only O(v^3) solutions can pass all tests?

Thanks