15 - 搬家

Sylveon

原題：http://hoj.twbbs.org/judge/problem/view/15
AC：http://hoj.twbbs.org/judge/judge/submission/31359

好吧，我不知道正解，原本想說用floyd來做，可是遇到無向圖判環就壞掉了，所幸做了一個 [tex]O(kV^4)[/tex] 暴力來試試看就AC了，可能常數夠小吧。 因為題目中有重邊，要記得扣除留最小邊，之後枚舉所有邊[tex](i,j)[/tex]，將邊[tex](i,j)[/tex]扣除後，做i到j的最短路，全部取最小就好了。

[sojcodepad]e4360afc[/sojcodepad]

domen111

這題用dijkstra快了不少，等一下再研究O(N^3)的解法

Dijkstra: 372ms
http://hoj.twbbs.org/judge/judge/submission/31429
http://ideone.com/HcKeWJ

SPFA: 558ms
http://hoj.twbbs.org/judge/judge/submission/31410

Bellmond-Ford: TLE
http://hoj.twbbs.org/judge/judge/submission/31433