ENG  RUSTimus Online Judge
Online Judge
Problems
Authors
Online contests
About Online Judge
Frequently asked questions
Site news
Webboard
Links
Problem set
Submit solution
Judge status
Guide
Register
Update your info
Authors ranklist
Current contest
Scheduled contests
Past contests
Rules
back to board

Discussion of Problem 1325. Dirt

Pages: Previous 1 2
Re: 1 BFS for finding shortest amount of boot change. Another one for shortest path.
Posted by Denis Koshman 21 Aug 2008 04:00
Try this test:

6 5
1 3
6 3
11111
12222
11112
12222
11112
22222

Correct answer: 7 1

So, after 1st BFS both components stay alive. What would prevent 2nd BFS from going a vertical line and output "6 1" while assumed path yields "6 5"?
Re: I used Dijkstra algorithm with Heap.
Posted by SkorKNURE 16 Nov 2008 22:13
Dijkstra via STL priority_queue<> ~0.25 sec
Dijkstra via hand-written heap implemented with change_priority() function ~ 0.125 sec
Re: 1 BFS for finding shortest amount of boot change. Another one for shortest path.
Posted by Ta'al 15 May 2014 13:37
I'm sorry, but can anybody describe me 2nd BFS? I spent a lot of time trying, but it give me wrong answer on some tests.
Pages: Previous 1 2