[HOJ] 9 - 大麥克的世界旅行

很明顯的它是一個


單源最短路單向邊、有負邊、需判斷負還

只不過這個最短路的計算方式是：路徑上所有數乘起來
其實只要把它取log就會發現加法乘法是一家~

(不過取log有時候會讓浮點誤差擴大 ， 尤其原本都只有整數的時候)


解1：
用Bellman-Ford 求A~B的最短路再把+換*就行了~

然後要小心點誤差
一般 Bellman-Ford + double 爆下去會WA
要開 long double 才會過
另外一個方法是把權重全部先取log
但其實取log個過程就可能會加大浮點誤差


解2：
Bellman-Ford 有點慢 ， 改用SPFA (Bellman-Ford 的 佇列優化) (Label Correcting Algorithm)
關於SPFA：nocow、演算法筆記
這題用了 SPFA 之後只要開 double 就會過，我沒深入研究原因，給有興趣的人自己想




AC：http://hoj.twbbs.org/judge/judge/submission/25367
CODE：