Page 1 of 4

10816 - Travel in Desert

Posted: Sun Feb 13, 2005 11:07 pm
by Sanny
Hi all,
Can you tell me what are the tricky cases in this problem. I thought it was a pretty straightforward shortest path problem. I used Floyd Warshall and got 7 WAs during the contest :evil: . I also saw that many people got WA many times in this problem.

Regards

Sanny

Posted: Mon Feb 14, 2005 2:53 am
by liulike
up
I also got many WAs
:evil:

Posted: Mon Feb 14, 2005 5:20 am
by Adrian Kuegel
It is probably not one tricky case that results in your WA, it is probably the totally wrong algorithm. That is what happened to me during the contest, I didn't think much because I thought it is an easy problem. Only after a lot of WA I realised my mistake.
Consider for example this test case:
3 3
1 3
1 2 10.0 10.0
1 2 11.0 9.0
2 3 11.0 10.0

Answer should be:
1 2 3
19.0 11.0

Posted: Mon Feb 14, 2005 5:36 am
by Observer
To decide where to go, they will pick a route that the highest temperature is minimized. If more than one route satisfy this criterion, they will choose the shortest one.
I think the line itself is a very good description of the algorithm (OUR algorithm I mean) :)

Posted: Mon Feb 14, 2005 8:57 pm
by Pavel Nalivaiko
Hi!
Solving this problem, I stored all possible temperatures in the array, sort it in the ascending order, and then start to solve this problem for a fixed temperature using simple Dijkstra algorithm until i found a temperature where solution exist.
This algorithm can be upgraded using binary search, but it got AC without it.

But if anybody knows how to solve this problem using only one Dijkstra (or may be Floyd-Warshall ) iteration, I'll be glad to hear this solution.

Posted: Mon Feb 14, 2005 9:38 pm
by Adrian Kuegel
You can do it with two dijkstras like Observer suggested. I doubt you can do it with one.

Posted: Mon Feb 14, 2005 10:27 pm
by Pavel Nalivaiko
Adrian Kuegel wrote:You can do it with two dijkstras like Observer suggested. I doubt you can do it with one.
Hmm.. I missed something?
Where is his suggestion about this problem? Give me a link, please.

Posted: Mon Feb 14, 2005 10:41 pm
by Sanny
Just solved this problem. And after solving this I must thank the problemsetter for this good and tricky problem. I used two Bellman Ford this time. First to find the minimum temperature and second to find the minimum distance.

Posted: Mon Feb 14, 2005 10:51 pm
by Adrian Kuegel
Pavel Nalivaiko wrote: Hmm.. I missed something?
Where is his suggestion about this problem? Give me a link, please.
Observer wrote:
To decide where to go, they will pick a route that the highest temperature is minimized. If more than one route satisfy this criterion, they will choose the shortest one.
I think the line itself is a very good description of the algorithm (OUR algorithm I mean) :)
And Sanny described it in more detail.

Posted: Mon Feb 14, 2005 11:46 pm
by little joey
Pavel Nalivaiko wrote:Hi!
Solving this problem, I stored all possible temperatures in the array, sort it in the ascending order, and then start to solve this problem for a fixed temperature using simple Dijkstra algorithm until i found a temperature where solution exist.
This algorithm can be upgraded using binary search, but it got AC without it.

But if anybody knows how to solve this problem using only one Dijkstra (or may be Floyd-Warshall ) iteration, I'll be glad to hear this solution.
You don't need Dijkstra the first time, but you can use a (simpler and faster) BFS to check if a path exists for a given max. temperature. Then use one Dijkstra to find the shortest path.

Posted: Tue Feb 15, 2005 7:26 am
by lord_burgos
input

Code: Select all

10 100
1 10
2 8 0.1 33.5
10 5 35.9 27.9
3 5 14.6 10.6
2 8 49.2 36.2
6 3 43.7 2.8
2 5 15.4 30.3
2 7 39.6 11.9
8 7 3.9 37.2
10 3 30.0 6.8
6 5 31.2 30.4
3 4 16.5 7.4
4 9 14.5 34.8
3 8 36.0 3.8
4 2 27.9 33.0
7 6 34.3 19.1
9 7 44.3 24.1
5 9 30.6 24.7
1 10 35.1 37.1
7 2 4.9 39.4
10 4 45.5 8.5
7 1 37.7 16.7
2 9 44.0 14.5
7 4 3.9 33.8
9 3 4.2 13.0
4 6 15.9 24.0
5 1 30.7 37.8
4 7 24.6 22.2
5 3 33.0 27.1
8 4 1.3 29.8
7 1 13.7 36.2
6 8 7.5 5.6
2 3 15.1 15.1
2 5 43.1 36.7
8 2 33.8 0.8
6 10 25.9 21.0
2 9 44.7 2.3
7 1 16.9 1.4
1 2 15.6 36.3
1 10 3.8 2.5
9 4 4.2 39.6
3 1 33.7 29.2
5 1 2.2 19.7
9 10 48.5 6.9
2 5 50.0 5.4
1 9 46.8 12.8
9 4 48.4 24.9
8 2 11.8 31.1
4 5 11.7 31.0
6 2 25.0 20.1
10 7 30.4 39.9
5 9 11.0 24.5
10 3 48.6 39.6
4 8 0.4 11.5
9 1 11.9 25.9
1 7 28.2 39.9
10 9 15.8 1.0
9 3 18.0 3.9
1 8 19.2 35.9
6 9 1.2 35.7
3 5 5.6 27.3
9 7 38.7 36.3
6 4 14.3 27.0
5 7 49.9 28.2
3 2 20.0 2.2
8 7 39.0 29.3
6 3 1.1 20.1
4 10 18.9 26.2
2 10 42.4 5.6
3 6 28.6 18.3
9 7 25.8 21.8
10 5 19.0 12.2
7 10 19.3 36.9
5 10 1.3 24.2
6 1 25.4 11.9
10 4 49.7 28.0
8 10 43.8 15.0
7 10 19.6 19.4
8 7 10.6 28.7
9 3 23.5 5.6
5 2 17.2 11.7
7 4 35.6 31.4
6 4 30.9 11.3
3 6 25.7 31.4
2 9 48.3 4.7
2 5 22.3 39.7
10 2 45.1 33.6
4 7 16.0 4.5
3 10 2.5 5.4
5 1 15.0 34.6
7 4 2.3 7.5
8 6 39.2 35.9
3 6 41.5 7.8
3 10 7.1 23.4
9 8 27.1 17.4
4 9 48.6 39.3
3 1 12.8 1.4
3 10 12.6 12.8
4 5 47.3 22.4
4 3 9.4 30.6
6 2 14.3 9.3
10 100
1 10
3 7 40.1 26.5
8 1 47.5 1.4
6 4 26.1 11.2
7 8 5.1 8.6
1 5 12.5 29.6
10 6 19.5 17.7
9 3 46.7 17.2
9 4 48.5 25.2
9 5 15.3 32.0
1 8 42.7 26.1
1 8 31.6 17.1
7 8 25.9 4.4
5 10 8.7 28.3
6 8 47.5 37.8
6 8 42.9 3.0
4 1 46.3 10.3
4 7 26.2 13.8
5 1 11.7 20.3
1 7 27.2 21.2
2 8 2.1 35.4
1 5 26.4 18.9
1 2 33.0 26.3
1 4 7.9 15.9
6 8 20.1 27.8
9 10 26.1 30.4
8 5 10.9 7.8
4 8 35.1 20.2
1 9 38.5 19.4
6 1 20.5 31.2
6 7 35.1 7.3
4 6 21.7 15.7
7 8 35.8 12.7
8 2 36.2 27.0
7 3 11.3 1.8
8 7 4.2 38.6
4 10 6.6 23.0
10 3 35.6 29.7
4 3 23.5 38.5
5 3 37.0 25.8
3 4 48.4 20.8
2 6 34.9 6.8
6 9 14.3 22.4
5 2 17.6 34.2
10 6 37.1 2.2
7 5 28.4 0.6
1 9 20.2 28.0
4 5 3.5 3.8
7 4 20.6 17.7
3 9 30.1 28.2
4 2 35.6 25.6
2 8 17.9 2.5
3 4 17.4 29.7
1 4 7.3 7.6
9 1 43.3 21.8
3 6 33.2 37.0
1 9 9.1 28.6
8 10 14.6 39.1
4 5 24.1 25.2
5 9 26.0 33.6
3 6 18.2 6.5
4 10 10.9 17.6
3 8 5.7 35.0
2 8 4.2 6.8
10 1 17.5 21.4
2 8 18.4 21.6
4 3 10.2 22.5
3 10 42.9 27.1
8 5 28.7 7.6
9 1 34.8 28.8
5 4 16.4 2.2
7 4 17.2 21.1
10 1 4.3 16.5
10 4 20.5 39.2
9 3 20.6 35.1
6 10 42.3 30.4
9 8 14.9 38.5
2 5 7.6 11.4
6 3 17.9 34.7
10 3 48.6 12.0
10 5 4.1 6.6
6 9 37.1 31.9
2 4 47.3 33.3
3 8 26.4 17.1
2 4 2.8 2.4
1 10 6.6 1.6
9 4 8.9 14.8
4 8 46.4 1.0
10 2 34.3 38.9
9 1 25.9 2.2
5 9 19.1 14.7
10 4 12.1 23.1
9 8 28.4 13.7
6 7 3.9 38.6
4 10 24.9 2.5
4 10 26.7 25.8
5 6 22.7 11.9
2 6 0.2 35.6
10 7 1.6 18.5
5 3 41.4 7.6
3 7 7.3 34.9
output (is correct ?)

Code: Select all

1 5 10
43.9 2.2
1 10
16.5 5.1

Posted: Tue Feb 15, 2005 7:34 am
by liulike
My output is:

Code: Select all

1 5 10
43.9 2.2
1 10
16.5 4.3
But I got wa again and again:(

Posted: Tue Feb 15, 2005 7:56 am
by Observer
liulike's output is correct. ("+ oil", liulike :) )

Posted: Tue Feb 15, 2005 8:09 am
by lord_burgos
Thanks i got ac, i'm implement kruskal first and afther dijkstra :P

Posted: Tue Feb 15, 2005 8:57 am
by Pavel Nalivaiko
little joey wrote: You don't need Dijkstra the first time, but you can use a (simpler and faster) BFS to check if a path exists for a given max. temperature. Then use one Dijkstra to find the shortest path.
Ah.. Silly of me :oops: :oops:
Adrian Kuegel wrote:
Observer wrote:
To decide where to go, they will pick a route that the highest temperature is minimized. If more than one route satisfy this criterion, they will choose the shortest one.
I think the line itself is a very good description of the algorithm (OUR algorithm I mean) :)
And Sanny described it in more detail.
Oh.. I thought that Observer quotated the problem descriprion :D
But now I understand that solution with two dijkstras lies not far from this :D