作者chienmin18 (chienmin)
看板Prob_Solve
標題[問題] TOI2008 4. 地道問題
時間Tue Feb 17 23:42:22 2009
題目：
http://cat.nknush.kh.edu.tw/ZeroJudge/ShowProblem?problemid=b117
這題是在求最短路徑的
但是點數最大到1000000
所以應該不可能用 弗洛伊德演算法
而且題目只要求 1-2+2-1+1-3+3-1+1-4+4-1+.....
所以我把單向圖以1當起點的存一次 以1終點的反過來在存一次
用dijkstra演算法 各做了一次
這樣的作法應該是對的吧？
但是傳上去WA
有人能幫我看一下嗎？
CODE：
http://src.wtgstudio.com/?Vw5F0O
--
※ 發信站: 批踢踢實業坊(ptt.cc)
◆ From: 59.114.136.194
※ 編輯: chienmin18 來自: 59.114.136.194 (02/17 23:43)
1F：推 pigalan:答案可能會超過int儲存的範圍~ 建議使用long long 02/18 22:56
2F：→ chienmin18:嗯 有試過了 不過還是WA~ 02/18 23:33
3F：→ LinkCar:這題看起來不像最短路徑阿?? 每個點都要去的最少花費 02/23 12:18
4F：→ LinkCar:看懂題目 原來是一一帶 02/23 12:22
6F：→ godgunman:有測資 自己測就知道了 02/27 01:24