程式解題社網站 程式解題社網站上線了！
NTUCPC OJ 現在支援 Rust ！
NTUCPCPC 2026 初賽 & 決賽題目已公開！ 連結
YTP 2026 題目已公開！ 連結
1507 . 小 Y 與小 P 的大冒險
TopCoder
Tags
Description
小 Y 和小 P 要從城鎮 $1$ 出發，前往城鎮 $N$。整個地圖上有 $N$ 個城鎮與 $M$ 條雙向道路，其中第 $i$ 條道路連接城鎮 $u_i$ 與城鎮 $v_i$，並且有一個危險係數 $w_i$。
對於一條從城鎮 $1$ 走到城鎮 $N$ 的路徑，我們定義這條路徑的危險程度為路徑上所有道路中危險係數的最大值。
小 Y 隨身帶著一個法寶，最多可以使用 $k$ 次；每次使用可以選擇一條道路，把它的危險係數變成 $0$。
小 Y 和小 P 想要事先規劃好路線，並決定要對路線上的哪些道路使用法寶，使得最終路徑的危險程度盡量小。請幫他們求出，在最多使用 $k$ 次法寶的情況下，從城鎮 $1$ 走到城鎮 $N$ 的路徑，危險程度最小可以是多少。如果無論如何都無法從城鎮 $1$ 走到城鎮 $N$，請輸出 $-1$。
Input Format
輸入第一行有三個整數 $N, M, k$，代表城鎮的數量、道路的數量，以及法寶最多可以使用的次數。
接下來 $M$ 行，第 $i$ 行有三個整數 $u_i, v_i, w_i$，代表第 $i$ 條道路連接城鎮 $u_i$ 與城鎮 $v_i$，危險係數為 $w_i$。道路可能重複（兩個城鎮間可能有多條道路），但保證沒有自環（$u_i \neq v_i$）。
- $2 \leq N \leq 2 \times 10^ 5$
- $1 \leq M \leq 2 \times 10^ 5$
- $0 \leq k \leq M$
- $1 \leq u_i, v_i \leq N$
- $u_i \neq v_i$
- $1 \leq w_i \leq 10^ 9$
- 兩個城鎮之間可能有多條道路。
Output Format
輸出一行一個整數，代表在最多使用 $k$ 次法寶的情況下，從城鎮 $1$ 走到城鎮 $N$ 的路徑，危險程度的最小值；若無法從城鎮 $1$ 走到城鎮 $N$，輸出 -1。
Sample Input 1
4 4 1 1 2 5 2 4 5 1 3 1 3 4 100
Sample Output 1
1
Sample Input 2
5 2 2 1 2 5 3 4 5
Sample Output 2
-1
Hints
範測 1 解釋：
選擇路線 $1 \to 3 \to 4$，並對危險係數為 $100$ 的道路（城鎮 $3$ 與城鎮 $4$ 之間）使用一次法寶，把它的危險係數變成 $0$。這條路徑上的道路危險係數分別為 $1$ 和 $0$，因此危險程度為 $1$。可以證明沒有辦法讓危險程度比 $1$ 更小。
範測 2 解釋：
城鎮 $1, 2$ 之間、城鎮 $3, 4$ 之間各自有道路相連，但這兩群城鎮彼此沒有任何道路連接，而城鎮 $5$ 也沒有任何道路。因此無論使用多少次法寶，都無法從城鎮 $1$ 走到城鎮 $5$，輸出 $-1$。
Problem Source
2026 YTP 高中組決賽 p6
Subtasks
| No. | Testdata Range | Constraints | Score |
|---|---|---|---|
| 1 | 0~1 | 範例測試資料 | 0 |
| 2 | 2~16 | $N \leq 5$，$M \leq 20$ | 2 |
| 3 | 17~26 | $k = 0$ | 3 |
| 4 | 0~39 | 無額外限制 | 10 |