b258:
安全路線
Content
在一個遙遠的土地上，分佈著 N 個不同的國家，這些國家我們暫且同 1 至 N 作為其代號。
而你則是編號 1 這個國家的總統。有部份國家之間有公路相連。
每條公路都是雙向的，而兩個不同的國家之間最多只有一條公路相連。
所有的國家都可以通過這些公路所一個國家去到另一個國家。
由於當地正發生一場區域大戰，情況非常不安定。你決定要招回所有駐其他國家的外交人員。
並非所有國家都有外交人員，只有小部國家有外交人員。
目前你正在規劃這些人員回國的路線。
由於戰亂的關係，你為每個國家分配一個危險指數，危險指數是一個非負整數，其值越大表示該國家越危險。
你自己的國家及原本駐有外交人員的國家的危險指數都為 0。其他國家的危險指數均大於 0。
你希望為這些外交人員規劃一條回國的路徑，使得沿途所經的所有國家的危險指數總和為最低者。
若有多條路可以規劃，則取一條總距離為最短的路線。
Input
輸入的數據中有若干組測試數據，每組數據如下:
- 數據的第一行有兩個正整數 N，K， N 代表國家的數目，而 K 則代表公路的數目。(2 ≤ N ≤ 1000 及 K ≤ 2N)
- 其後的一行中有 N 個非負整數，順序代表 N 個國家的危指數。而第一個整數必為 0，因它代表你自己的國家，隨後的 N-1 個數中，有部份為 0，這些危險指數為 0 的國家代表在該國有外交人員。
- 隨後有 K 行，每行都有三個正數 a~b~d，代表在國家 a 和 b 之間有一條長度為 d 的公路相連。國家的編號是 1 … N，而你的國家編號為 1。
最後一組數據只有兩個 0，它們代表輸入的完結。
Output
對應於每一組輸入數據，輸出若干行，每行代表招回一位外交人員時他的路徑資料，其格式如下:
- 每行有兩個整數 I~P，I 是回國時所用路徑的危險指數的總和，P 為該路徑的總長度。
數據輸出的次序要跟據外交人員原所在的國家編號順序排列。
Sample Input
#1
7 8 0 4 3 2 0 7 0 1 2 3 1 3 4 2 5 1 2 4 6 4 6 5 4 7 2 6 7 3 3 7 20 0 0
Sample Output
#1
4 4 3 24
測資資訊：
記憶體限制：
64
MB
不公開 測資點#0 (9%): 1.0s , <1K
不公開 測資點#1 (9%): 1.0s , <1M
不公開 測資點#2 (9%): 1.0s , <1M
不公開 測資點#3 (9%): 1.0s , <1M
不公開 測資點#4 (9%): 1.0s , <1M
不公開 測資點#5 (9%): 1.0s , <1M
不公開 測資點#6 (9%): 1.0s , <1M
不公開 測資點#7 (9%): 1.0s , <1M
不公開 測資點#8 (9%): 1.0s , <1M
不公開 測資點#9 (9%): 1.0s , <1M
不公開 測資點#10 (10%): 1.0s , <1M
不公開 測資點#0 (9%): 1.0s , <1K
不公開 測資點#1 (9%): 1.0s , <1M
不公開 測資點#2 (9%): 1.0s , <1M
不公開 測資點#3 (9%): 1.0s , <1M
不公開 測資點#4 (9%): 1.0s , <1M
不公開 測資點#5 (9%): 1.0s , <1M
不公開 測資點#6 (9%): 1.0s , <1M
不公開 測資點#7 (9%): 1.0s , <1M
不公開 測資點#8 (9%): 1.0s , <1M
不公開 測資點#9 (9%): 1.0s , <1M
不公開 測資點#10 (10%): 1.0s , <1M
Hint ：
Tags:
| ID | User | Problem | Subject | Hit | Post Date |
| 1679 | b258 | 27 | 2024-10-24 19:06 |