| layout | title | date | tags | |||
|---|---|---|---|---|---|---|
post |
[POJ] 3767 - I Wanna Go Home |
2011-11-23 |
|
某國家正在面臨戰爭，國家中的城市分為兩派，分別支持不同的領導者。有一個商人想要回家，他要從城市 A 回到城市 B。現在要請你規劃出他最快能在多少時間內回到家。
- 城市數量 N，2 ≤ N ≤ 600
- 道路數量 M，0 ≤ M ≤ 10,000
- 道路花費時間 T，1 ≤ T ≤ 500
- 每一條路線皆為雙向邊
- 領導人的編號分別為 1 與 2
- 假設商人總是要從編號為 1 的城市回到編號為 2 的城市
- 編號為 1 的城市總是領導人 1 的派系，而編號為 2 的城市總是為領導人 2 的派系
- 僅能通過一條連結不同派系城市的路
對於每筆測試資料的第一行輸入一個整數 N，表示該國家城市數量，若此數為 0 表示為測試資料結束。接著第二行輸入整數 M，代表該國家的道路數量。接著有 M 行，每行有三個數字 A, B, T，表示城市 A 與城市 B 之間有一條路徑，且需要耗費 T 的時間。測試資料的最後一行會輸入 N 個整數，這 N 個整數分別表示為各城市所代表的派系。
對於每一筆測試資料，輸出一個整數，表示該商人回家的最短時間。若無解時，請輸出 -1。
在給定的條件中，我們可以發現，規劃出來的路線，僅能從派系 1 的城市走到派系 2 的城市，或是同派系之間的城市之間往返。因此可以看出不能從派系 2 的城市往派系 1 的城市走。（由僅能走一條跨派系的路線與起點城市皆屬於派系 1，終點城市皆屬於派系 2 可得知）
於是我們就可以針對給定的圖做點處理。原本整張圖上的邊皆為雙向邊，我們將連結兩個派系的邊化為單向邊，使該邊僅能由派系 1 的城市往派系 2 的城市。接著在使用一般的 shortest path 的演算法套入，即可解決此題。
<script src="https://gist.github.com/KuoE0/6154538.js"></script>Time Complexity: O(N × log N)
Source code on gist.