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

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

1 3 300
3 1 10

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

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.

0.343 sec.
Just to let you know. ;)

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 -> 4 -> 1 подходит.

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

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

Problem statement, tests and time limit were changed. Read the Site news for more information.

= =！If there are some place wrong in my case，please notice me.
100 100
2 24 100
65 92 100
9 56 100
40 55 100
68 14 100
76 21 100
21 15 100
82 86 100
3 40 100
72 40 100
92 45 100
39 82 100
84 72 100
44 63 100
88 17 100
62 21 100
41 15 100
73 82 100
36 70 100
33 22 100
78 60 100
57 34 100
66 71 100
56 83 100
93 56 100
25 70 100
99 64 100
68 39 100
85 70 100
86 29 100
91 67 100
52 18 100
4 44 100
81 97 100
59 38 100
17 78 100
73 83 100
98 44 100
45 37 100
11 9 100
97 99 100
63 94 100
75 54 100
6 7 100
84 15 100
97 19 100
30 90 100
51 39 100
42 9 100
88 16 100
70 38 100
70 64 100
5 82 100
37 41 100
76 95 100
69 18 100
72 54 100
100 55 100
28 4 100
60 1 100
8 86 100
1 66 100
87 53 100
87 27 100
18 79 100
14 19 100
21 41 100
93 8 100
31 100 100
63 74 100
48 10 100
62 74 100
42 59 100
31 50 100
97 21 100
15 93 100
64 16 100
37 56 100
88 41 100
99 16 100
76 19 100
89 61 100
97 18 100
47 73 100
9 29 100
100 38 100
83 15 100
94 47 100
72 37 100
3 38 100
51 89 100
63 55 100
84 22 100
14 95 100
64 16 100
99 8 100
39 37 100
15 78 100
11 22 100
64 44 100

заменил
std::ends на ' '
и сразу "Accepted"

ну как так можно?


Edited by author 11.07.2013 17:18

1) What does it mean by two-way road?

Lets say I use road 1 and 3 in the sample..
To go from 1 to 3, it costs 300 and from 3 to 1 it is just 10. In that case we dont have route to go from 5 to 3. Then why is the answer correct?

1 3 5 2

1 to 3 -> 300
3 to 5 -> (No route, but taking 5 to 3 value) 300 + 20
5 to 2 -> (Again no route, taking 2 to 5 value) 300 + 20 + 15
2 to 1 -> (No route, using 1 to 2) 300 + 20 + 15 + 16 => 351

But consider 1 2 5 3

1 to 2 -> 16
2 to 5 -> 16 + 15
5 to 3 -> 16 + 15 + 20
3 to 1 -> 16 + 15 + 20 + 10 which is just 61

Could someone please explain why it is 1 3 5 2 and not 1 2 5 3?