|
|
вернуться в форумShould I use Dijkstra's algorithm several times for each friend or just floyd-warshall? ..? good q ..
but .. !
all the edge's cost's are 1 .. so .. :-)
use BFS .. for every friend from its starting position :-)
its n*k :-)
.. but i got WA 14 :-( ...
~~~~~~~~~~~~~~~~~~~~~~~~~~~
now i get it .. the WA's in the discuss are very useful :-)
and .. with my o(n*k)
i had .. 0.031 264 KB
Edited by author 13.09.2010 22:03
Edited by author 13.09.2010 22:03 Are you sure it's O(n*k)? I used DFS from every tramstop to find how much it costs for all of friends to meet here.
This test helped me a lot (it's funny to draw circles):
13 5
3 1 2 3
3 4 5 3
3 6 7 3
3 8 9 3
8 10 4 11 6 12 8 13 1
I corrected all mistakes by adding different situations on this tram-map :) |
|
|
