| layout | title | date | tags | ||||
|---|---|---|---|---|---|---|---|
post |
[POJ] 3259 - Wormholes |
2011-05-17 |
|
題目網址：3259 - Wormholes
Farmer John 有 N 座田地，這些田之間有 M 條路徑。並且發現了在某些田上有蟲洞，共有 W 個蟲洞。蟲洞就是個可以穿越時空回到過去的一條路。
Farmer John 想要穿越時空回到過去。田地之間的道路為雙向的，而蟲洞是連接著田地的單向道路。給定田地與蟲洞的資訊，求 Farmer John 是否能成功回到過去。
- 田地數量 N, 1 ≤ N ≤ 500
- 道路數量 M, 1 ≤ M ≤ 2,500
- 蟲洞數量 W, 1 ≤ W ≤ 500
測試資料由一整數 F 開始，表示接下來有 F 組測試資料。
每一筆測試資料由三個整數開始 N, M, W，如同前面的敘述，分別為田地數量、道路數量以及蟲洞數量。接下來會有 M + W 行，每行有三個整數 S, E, T。前 M 行為田地之間的道路，表示 S 到 E 需要 T 時間，田地間的道路是雙向的，因此 E 到 S 也需要 T 時間。接下來的 W 行為蟲洞，表示 S 到 E 可以倒退 T 時間，注意，蟲洞是單方向的。
對於每一筆測試資料，輸出只有一行，若 Farmer John 可以成功回到過去，即輸出 YES，否則輸出 NO。
要回到過去就是要使回到起點的時間須為負數。若回到起點的時間是為負數，我們可以一直經由這些路徑，使得回到起點的時間越來越早。
因此很明顯的就是將所給的資訊建立為一張 graph，其中一般路徑就設為是雙向的路徑且權重為 T，而蟲洞就設為單向的路徑且權重為 -T，再利用 Bellman-Ford 或 SPFA 求是否存在負環即可。
注意會有重邊，因此建議用 adgacent-list 的方式儲存。
<script src="https://gist.github.com/KuoE0/1619811.js"></script>Time Complexity: O(N × (M + W))
Source code on gist.