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

Regards
Sanny
Moderator: Board moderators
I think the line itself is a very good description of the algorithm (OUR algorithm I mean)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.
Pavel Nalivaiko wrote: Hmm.. I missed something?
Where is his suggestion about this problem? Give me a link, please.
And Sanny described it in more detail.Observer wrote:I think the line itself is a very good description of the algorithm (OUR algorithm I mean) :)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.
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.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.
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
Code: Select all
1 5 10
43.9 2.2
1 10
16.5 5.1
Code: Select all
1 5 10
43.9 2.2
1 10
16.5 4.3
Ah.. Silly of melittle 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.
Oh.. I thought that Observer quotated the problem descriprionAdrian Kuegel wrote:And Sanny described it in more detail.Observer wrote:I think the line itself is a very good description of the algorithm (OUR algorithm I mean)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.