竹園論壇

標題: 15 - 搬家 [打印本頁]

作者: Sylveon 時間: 2015-3-12 17:15
標題: 15 - 搬家
原題：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 時間: 2015-3-14 12:39
本帖最後由 domen111 於 2015-3-14 14:03 編輯

這題用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

歡迎光臨竹園論壇 (http://forum.tfcis.org/)