e930: pD. 最少過路費
Tags :
Accepted rate : 13人/21人 ( 62% ) [非即時]
評分方式:
Tolerant

最近更新 : 2020-03-22 00:23

Content

現在有 n 個城市(編號 0 ~ n-1), m 條道路,
並且行經每條道路時都會有一定過路費需要索取。

你想要計算在有限步數 k 內,
從城市 0 走到 城市 n-1,最少需要的過路費總和。
若不可能則輸出 "impossible"

以下圖為例,從城市 0 走到城市 5:
當有限步數 k = 5,輸出 1 + 1 + 1 = 3
當有限步數 k = 2,輸出 6 + 7 = 13
當有限步數 k = 1,輸出 "impossible"

Input

第一行有三個整數 n, m, k (1 ≤ n ≤ 100000, 0 ≤ m ≤1000000, 0 ≤ k ≤ 100)
分別表示城市數、道路數、最多能走幾條路

接下來有 m 行,每行有三個整數 u, v, w (0 ≤ u, v ≤ n-1, 0 ≤ w ≤100)
分別表示起點、終點、過路費

Output

輸出從 0 走到 n-1 最少要花多少錢
若無法抵達,則輸出 "impossible"

Sample Input #1
6 6 5
0 1 1
0 2 6
1 3 1
1 4 5
2 5 7
3 5 1
Sample Output #1
3
Sample Input #2
6 6 2
0 1 1
0 2 6
1 3 1
1 4 5
2 5 7
3 5 1
Sample Output #2
13
Sample Input #3
6 6 1
0 1 1
0 2 6
1 3 1
1 4 5
2 5 7
3 5 1
Sample Output #3
impossible
測資資訊:
記憶體限制: 64 MB
公開 測資點#0 (10%): 10.0s , <10M
公開 測資點#1 (10%): 10.0s , <10M
公開 測資點#2 (10%): 10.0s , <10M
公開 測資點#3 (10%): 10.0s , <10M
公開 測資點#4 (10%): 10.0s , <10M
公開 測資點#5 (10%): 10.0s , <10M
公開 測資點#6 (10%): 10.0s , <10M
公開 測資點#7 (10%): 10.0s , <10M
公開 測資點#8 (10%): 10.0s , <1M
公開 測資點#9 (10%): 10.0s , <10M
Hint :
Tags:
出處:
2015大學學測推甄申請二階 [管理者:
mushroom.cs9... (mushroom)
]


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