內容
現在有 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"
輸入說明
第一行有三個整數 n, m, k (1 ≤ n ≤ 100000, 0 ≤ m ≤1000000, 0 ≤ k ≤ 100)
分別表示城市數、道路數、最多能走幾條路
接下來有 m 行，每行有三個整數 u, v, w (0 ≤ u, v ≤ n-1, 0 ≤ w ≤100)
分別表示起點、終點、過路費
輸出說明
輸出從 0 走到 n-1 最少要花多少錢
若無法抵達，則輸出 "impossible"
範例輸入
#1
6 6 5 0 1 1 0 2 6 1 3 1 1 4 5 2 5 7 3 5 1
範例輸出
#1
3
範例輸入
#2
6 6 2 0 1 1 0 2 6 1 3 1 1 4 5 2 5 7 3 5 1
範例輸出
#2
13
範例輸入
#3
6 6 1 0 1 1 0 2 6 1 3 1 1 4 5 2 5 7 3 5 1
範例輸出
#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
公開 測資點#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
提示 ：
標籤:
| 編號 | 身分 | 題目 | 主題 | 人氣 | 發表日期 |
|
沒有發現任何「解題報告」
|
|||||