藤原拓海是一名賽車手，為了備戰即將到來的秋名山比賽，他決定精進自己的駕駛技巧。
已知藤原會從編號 $0$ 的起點出發。由於他是一位技術純熟的車手，只要道路寬度不小於車的寬度，他就能順利通過。
藤原希望挑戰極限，因此想選擇越寬的車越好。
現在有 $n$ 個終點（編號為 $1 \sim n$），以及 $m$ 條雙向道路，每條道路以三元組 $(u_i,\;v_i,\;w_i)$ 表示，代表 $u_i$ 和 $v_i$ 之間有一條寬度為 $w_i$ 的道路。
藤原想知道對每一個終點 $j$，從起點 $0$ 出發到達終點 $j$ 的過程中，所能通行的最大車寬 $c_j$ 為多少，請你幫幫藤原吧！
(註：如果無法從起點到達終點 $j$，定義 $c_j=-1$)
$n\;m$
$u_1\;v_1\;w_1$
$u_2\;v_2\;w_2$
$...$
$u_m\;v_m\;w_m$
$c_1\;c_2\;c_3\;...\;c_n$
4 4 1 0 4 0 2 5 1 3 8 0 3 6
6 5 6 -1
公開 測資點#0 (5%): 1.0s , <1K
公開 測資點#1 (5%): 1.0s , <1M
公開 測資點#2 (5%): 1.0s , <1M
公開 測資點#3 (5%): 1.0s , <1M
公開 測資點#4 (10%): 1.0s , <10M
公開 測資點#5 (10%): 1.0s , <10M
公開 測資點#6 (10%): 1.0s , <10M
公開 測資點#7 (10%): 1.0s , <10M
公開 測資點#8 (10%): 1.0s , <10M
公開 測資點#9 (10%): 1.0s , <10M
公開 測資點#10 (10%): 1.0s , <10M
公開 測資點#11 (10%): 1.0s , <10M
$Subtask\;1\quad$$#00$$\sim$$#03$ $(20\%)$：$1\leq n\leq 1000$，$0\leq u_i,\;v_i\leq n$，$1\leq w_i\leq 1000$
$Subtask\;2\quad$$#04$$\sim$$#11$ $(80\%)$：無特殊限制
對於所有測資，$1\leq n\leq 2\times 10^5$，$0\leq u_i,\;v_i\leq n$，$1\leq w_i\leq 2\times 10^5$，$m\leq min(2\times 10^5,\;\frac{n(n+1)}{2})$，$u_i\neq v_i$，且每組 $u_i,\;v_i$ 間最多只有一條路。
因為存在不少假解，故各個 $Subtask$ 要所有測資點通過才給分。
範例測資示意圖如下：
經由 $(0,3,6),\;(1,3,8)$，故 $c_1=6$
經由 $(0,2,5)$，故 $c_2=5$
經由 $(0,3,6)$，故 $c_3=6$
圖上無法從 $0$ 到達 $4$，故 $c_4=-1$
| 編號 | 身分 | 題目 | 主題 | 人氣 | 發表日期 |
沒有發現任何「解題報告」 |
|||||