Highways

Umm , the task is not that complicated , or is it?
I mean its purely a shortest path algorithm.
I chose Floyd-Warshall and it works for everything i come up with , but i fail on 7 out of 10 test cases. Can someone take a look at the code and give me advice ?

BTW: the code is pretty ugly and the implementation of th FW algo is kind of odd , but its correct (in theories :D)

Submision:
http://www.z-trening.com/new/www/html/submit.php?subm_stat=1&submit=7100051025

Isn't Floyd-Warshall complexity O(n^3) - it finds all the shortest path between all pairs of vertices? I don't know how can that algorithm be fast enough for this problem? Perhaps your Floyd algo isn't correct, I don't know. I can't see your solution because I haven't solved it myself.

Anyway, I think you should use Dijkstra's algorithm.

Floyd-Warshall is too slow for this task. Use Dijkstra with priority queue instead.

actualy FW isnt that slow , in my case most of the testcases run in time (about 0.7 s each)
but thats because of the odd implementation :D

EDIT: I redid the program with the BF algorithm
but it just works on 2 tests.

This old code was crap :D

I've done some more minor modification , but i just can't find the problem.

Could someone give me some testcases , i tried quite a lot of em....

your FW isn't good ... in FW alg you add new vertex in every step and look is some edge better with that vertex ...
your alg is more like dikstra, but it is important in what order you look vertex ...
you are looking vertex from 0 to n-1, but you should look from vertex with smallest distance to vertex with largest distance ...
i hope you understand me ...

just do dikstra with priority_queue ...

Yeah i realized that my whole code is a giant bug. I took like 3 lines from some old code , but when you analyze it , its a miracle that it works for 3 testcases :D.
Anyway thanks , ill do it with dijksta.

The dijkstras algo worked like a charm the essential part is just code it the way everybody does :D

what's test #3 does?

hmm, maybe, just maybe you can get overflow when you add something to your infinity. Try 20000000 as infinity instead of 2000000000.

still doesnt work, or is there something wrong with my dijkstra?

help
3rd test case

http://z-trening.com/submit.php?submit=7100355223&subm_code=1