10816 - Travel in Desert

Sanny · Post by **Sanny** » 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

liulike · Post by **liulike** » Mon Feb 14, 2005 2:53 am

up
I also got many WAs

Adrian Kuegel · Post by **Adrian Kuegel** » 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

Answer should be:
1 2 3
19.0 11.0

Observer · Post by **Observer** » 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)

Pavel Nalivaiko · Post by **Pavel Nalivaiko** » 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.

Adrian Kuegel · Post by **Adrian Kuegel** » 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.

Pavel Nalivaiko · Post by **Pavel Nalivaiko** » 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?
Where is his suggestion about this problem? Give me a link, please.

Sanny · Post by **Sanny** » 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.

Adrian Kuegel · Post by **Adrian Kuegel** » Mon Feb 14, 2005 10:51 pm

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.

little joey · Post by **little joey** » 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.

lord_burgos · Post by **lord_burgos** » 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

liulike · Post by **liulike** » Tue Feb 15, 2005 7:34 am

My output is:

Code: Select all

But I got wa again and again:(

Observer · Post by **Observer** » Tue Feb 15, 2005 7:56 am

liulike's output is correct. ("+ oil", liulike

)

lord_burgos · Post by **lord_burgos** » Tue Feb 15, 2005 8:09 am

Thanks i got ac, i'm implement kruskal first and afther dijkstra

Pavel Nalivaiko · Post by **Pavel Nalivaiko** » 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

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

But now I understand that solution with two dijkstras lies not far from this