Page 1 of 4

### 10816 - Travel in Desert

Posted: Sun Feb 13, 2005 11:07 pm
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 . I also saw that many people got WA many times in this problem.

Regards

Sanny

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

Posted: Mon Feb 14, 2005 5:20 am
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

1 2 3
19.0 11.0

Posted: Mon Feb 14, 2005 5:36 am
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
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
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
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?

Posted: Mon Feb 14, 2005 10:41 pm
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
Pavel Nalivaiko wrote: Hmm.. I missed something?
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
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
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
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
liulike's output is correct. ("+ oil", liulike )

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

Posted: Tue Feb 15, 2005 8:57 am
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