Обсуждение @ 1004. Экскурсия @ Timus Online Judge

thefourtheye Didnt understand the question clearly [3] // Задача 1004. Экскурсия 24 мар 2012 11:53

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?

2rf Re: Didnt understand the question clearly [2] // Задача 1004. Экскурсия 24 мар 2012 16:15

Both answers are correct. In first sample there are 2 two-way roads between crossings 1 and 3: one's length is 300 and the other's is 10. Of course, in optimal solution you will only use shortest road between some pair of crossings.

thefourtheye Re: Didnt understand the question clearly [1] // Задача 1004. Экскурсия 24 мар 2012 18:38

Hi 2rf,

Thanks a bunch for clarifying. Still I have a problem...

For the input found here http://www.fi.muni.cz/ceoi1999/trip/TRIP.I1

4 6
1 2 40
1 3 50
1 40 60
2 3 10
2 4 30
3 4 20

According to http://www.fi.muni.cz/ceoi1999/trip/TRIP.O1 Output should be 2 3 4, it seems

But my program generates 1 2 4 3 as the answer.

I don't know who is correct. Would you mind helping me again? :)

Edited by author 24.03.2012 18:40

2rf Re: Didnt understand the question clearly // Задача 1004. Экскурсия 25 мар 2012 00:40

This test is clearly incorrect: 4th line describes an edge connecting vertices 1 and 40. However, there are only vertices with numbers from 1 to 4. Most probably, 4th line should be "1 4 60". "2 3 4" is correct answer then.

Обсуждение задачи 1004. Экскурсия