|
|
back to boardDiscussion of Problem 1325. DirtRe: 1 BFS for finding shortest amount of boot change. Another one for shortest path. 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. 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. |
|
|