b258: 安全路線
Tags :
Accepted rate : 1人/1人 ( 100% ) [非即時]
評分方式:
Tolerant

最近更新 : 2024-05-10 10:55

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
Hint :
Tags:
出處:
MOIC2014MCS [管理者:
kulam@g.puic... (林建源)
]


ID User Problem Subject Hit Post Date
沒有發現任何「解題報告」