給 $n$ 個城市, $m$ 條雙向道路,
其中有$k$個城市為避難所，代表如果有發生天災的話，每個城市的人都要前往避難所
假設每個城市$x$到離自己的最近的避難所距離稱為$dis[x]$
(若城市$x$本身為避難所則$dis[x]=0$)
而有些城市的人可能因為距離太遠，來不及到避難所逃生，因此會有額外的救援直升機，會進行$r$次救援
每次救援可以直接將一個城市$x$的人直接送到避難所，現在問你當經過最多$r$次救援後，沒被救援的城市中，
離最近的避難所最遠的城市距離最小的為多少，即求最小的$max ( dis[x] ) $
$保證圖連通，無重邊、自環$
(此為範例測資原圖，粗線為避難所)
單筆測資
第一行有四個整數$n,m,k,r$
$n ( 1 \le n \le 2 \cdot 10^5)$
$m(n-1 \le m \le min(2 \cdot 10^5,\frac{n \cdot (n-1)}{2}))$
$k(1\le k < n)$
$r(0 \le r < n-k)$
第二行有$k$個數字$x_i(1 \le x_i \le n)$，代表$k$個避難所的編號，保證皆不重複
接下來的$m$行，每行有三個數字$u,v,w (1 \le u,v \le n，u \ne v，1 \le w \le 10^6)$，代表點$u$與點$v$雙向連通，並且權重為$w$
$保證圖連通，無重邊、自環$
subtask1 ( 7%) $w=1, 1 \le n*(n-k) \le 2 \cdot 10^5$
subtask2 (35%) $1 \le n*(n-k) \le 2 \cdot 10^5$
subtask3 (58%) 無額外限制
輸出經過$r$次救援後最小的$max(dis[x]),x \in (1 \sim n)$
7 7 2 1 2 3 1 2 3 1 3 2 1 6 3 2 3 1 2 5 2 3 4 3 6 7 1
5
不公開 測資點#0 (5%): 1.0s , <1M
不公開 測資點#1 (1%): 1.0s , <10M
不公開 測資點#2 (1%): 1.0s , <10M
不公開 測資點#3 (33%): 1.0s , <10M
不公開 測資點#4 (1%): 1.0s , <10M
不公開 測資點#5 (1%): 1.0s , <10M
不公開 測資點#6 (55%): 1.0s , <10M
不公開 測資點#7 (1%): 1.0s , <10M
不公開 測資點#8 (1%): 1.0s , <10M
不公開 測資點#9 (1%): 1.0s , <10M
範例測試中，把救援直升機去救援城市7的人，剩下沒被救援的城市中最遠的是城市6，距離為5(3+2)
| 編號 | 身分 | 題目 | 主題 | 人氣 | 發表日期 |
沒有發現任何「解題報告」 |
|||||