a577. C. 避難所 - 旦旦解題農場

內容

給 $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)$

範例輸入

範例輸出

測資資訊：

記憶體限制： 64 MB
不公開測資點#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)

標籤:

109學年度進階班下學期期末考

出處:

[管理者：

fdhs105285 (jakao)

]

編號	身分	題目	主題	人氣	發表日期
沒有發現任何「解題報告」