1838 . [IOI 2013] 作夢中 Dreaming
TopCoder
Tags
Description
當大地仍在創始，IOI連影子都不存在時期，發生了以下的故事。
水蛇(Serpent)住在一處擁有N個水洞的地方，水洞編號為 0, …, N - 1 。除此之外，有 M條雙向初始路徑，每條路徑連結一組的水洞讓水蛇可以通過。每一個水洞(不論直接或是間接)至多被一條路徑序列給連結著，但仍然有水洞可能都沒被任何的路徑給連結到(所以 M ≤ N-1 )。每條路徑會花掉水蛇特定的天數來通過，通過時間每條路徑有可能會不一樣。
水蛇的好友，袋鼠(Kangaroo)，希望可以挖出 N - M - 1 條新的路徑，讓水蛇可以在任意兩個水洞之間遊走。袋鼠可以在任意兩個水洞之間挖出新的路徑，而由袋鼠挖出的路徑，水蛇需要 L 天就可以通過。
另外，袋鼠希望水蛇在各水洞之間盡可能的快速移動。袋鼠將會挖出新的路徑，使得旅行於任兩個水洞之間所需要的時間最短。在袋鼠挖出新的路徑後，請你幫助水蛇和袋鼠計算出各水洞之間最長移動時間為何。
Input Format
本題有豆比測資，讀到「以歐哀夫」結束。
對於每比測資，第一行有三個數字N M L，分別表示水洞數目、初始路徑數、水蛇在新挖出的路徑移動所需的天數。
接下來有 M 行，每行三個數字Ai Bi Ti，表示第i個路徑連結著水洞Ai與水洞Bi，且需要Ti天的時間來通過。
限制：
1 ≤ N ≤ 100,000
0 ≤ M ≤ N-1
0 ≤ Ai, Bi ≤ N-1
1 ≤ Ti ≤ 10,000
1 ≤ L ≤ 10,000
14%的測資，M = N - 2 ，每個水洞只連有一條或是兩條的初始路徑。換句話說，只存在著兩組的相連水洞，每組相連的水洞中不存在分岔的路徑。
10%的測資，M = N-2 和 N ≤ 100。
23%的測資，M = N -2。
18%的測資，每個水洞至多連有一條初始路徑。
12%的測資，N ≤ 3,000。
23%的測資，沒有限制。
Output Format
輸出一個數字，表示在袋鼠挖出新的路徑後所有水洞之間的最大的移動時間(如敘述)。
Sample Input 1
0 8 4
8 2 2
2 7 4
5 11 3
5 1 7
1 3 1
1 9 5
10 6 3
Sample Output 1
Hints
上圖展示了最終的路徑圖。最長的移動時間是從水洞0移動到水洞11，需18天。
這已經是最低所需時間—無論袋鼠怎麼改變挖路徑的方法，都會產生至少一組水洞使得水蛇需要花費18天以上(含)才能通過。
Problem Source
IOI 2013
Subtasks
| No. | Testdata Range | Score |
|---|---|---|
| 1 | 0 | 1 |
| 2 | 1 | 14 |
| 3 | 2 | 10 |
| 4 | 3 | 23 |
| 5 | 4 | 18 |
| 6 | 5 | 12 |
| 7 | 6 | 22 |