## 10816 - Travel in Desert

All about problems in Volume 108. If there is a thread about your problem, please use it. If not, create one with its number in the subject.

Moderator: Board moderators

Sanny
Learning poster
Posts: 78
Joined: Sat Feb 14, 2004 3:59 pm
Location: BUET
Contact:

### 10816 - Travel in Desert

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
Learning poster
Posts: 52
Joined: Wed Jul 30, 2003 10:56 am
up
I also got many WAs
Guru
Posts: 724
Joined: Wed Dec 19, 2001 2:00 am
Location: Germany
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
Observer
Guru
Posts: 570
Joined: Sat May 10, 2003 4:20 am
Location: Hong Kong
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)
7th Contest of Newbies
Date: December 31st, 2011 (Saturday)
Time: 12:00 - 16:00 (UTC)
URL: http://uva.onlinejudge.org
Pavel Nalivaiko
New poster
Posts: 15
Joined: Sun Mar 07, 2004 7:47 pm
Location: Moscow, Russia
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.
Guru
Posts: 724
Joined: Wed Dec 19, 2001 2:00 am
Location: Germany
You can do it with two dijkstras like Observer suggested. I doubt you can do it with one.
Pavel Nalivaiko
New poster
Posts: 15
Joined: Sun Mar 07, 2004 7:47 pm
Location: Moscow, Russia
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?
Sanny
Learning poster
Posts: 78
Joined: Sat Feb 14, 2004 3:59 pm
Location: BUET
Contact:
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.
Guru
Posts: 724
Joined: Wed Dec 19, 2001 2:00 am
Location: Germany
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.
little joey
Guru
Posts: 1080
Joined: Thu Dec 19, 2002 7:37 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
New poster
Posts: 43
Joined: Mon Oct 13, 2003 4:54 pm
Location: Mexico
Contact:
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
``````
Last edited by lord_burgos on Tue Feb 15, 2005 7:53 am, edited 1 time in total.
liulike
Learning poster
Posts: 52
Joined: Wed Jul 30, 2003 10:56 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:(
Observer
Guru
Posts: 570
Joined: Sat May 10, 2003 4:20 am
Location: Hong Kong
liulike's output is correct. ("+ oil", liulike )
7th Contest of Newbies
Date: December 31st, 2011 (Saturday)
Time: 12:00 - 16:00 (UTC)
URL: http://uva.onlinejudge.org
lord_burgos
New poster
Posts: 43
Joined: Mon Oct 13, 2003 4:54 pm
Location: Mexico
Contact:
Thanks i got ac, i'm implement kruskal first and afther dijkstra
Pavel Nalivaiko
New poster
Posts: 15
Joined: Sun Mar 07, 2004 7:47 pm
Location: Moscow, Russia
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