Обсуждение @ 1325. Грязь @ Timus Online Judge

Re: 1 BFS for finding shortest amount of boot change. Another one for shortest path.

Послано Denis Koshman 21 авг 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.

Послано SkorKNURE 16 ноя 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.

Послано Ta'al 15 май 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.

Страницы: Предыдущая 1 2

Обсуждение задачи 1325. Грязь