TopCoder

User's AC Ratio

76.7% (46/60)

Submission's AC Ratio

25.1% (98/391)

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

12 8 2
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

18

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

Testdata and Limits

No. Time Limit (ms) Memory Limit (VSS, KiB) Output Limit (KiB) Subtasks
0 2000 65536 262144 1
1 2000 65536 262144 2
2 2000 65536 262144 3
3 2000 65536 262144 4
4 2000 65536 262144 5
5 2000 65536 262144 6
6 2000 65536 262144 7