Discussion @ 1325. Dirt @ Timus Online Judge

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

Discussion of Problem 1325. Dirt