Login with GitHub. Nope?
修正 C++ 的程式碼在使用一定量動態記憶體後會產生 RF 的問題 @ 2019/12/6 4:45pm NeoHOJ 強勢復活中 (Open beta)
Submit　　Ranklist

Problem : 288 - Dreaming

Problem Statistics

Solved Member: 44　　Submission: 326　　User Tried: 44

Statement:

當大地仍在創始，IOI連影子都不存在時期，發生了以下的故事。

水蛇(Serpent)住在一處擁有N個水洞的地方，水洞編號為 0, …, N - 1 。除此之外，有 M條雙向初始路徑，每條路徑連結一組的水洞讓水蛇可以通過。每一個水洞(不論直接或是間接)至多被一條路徑序列給連結著，但仍然有水洞可能都沒被任何的路徑給連結到(所以 M ≤ N-1 )。每條路徑會花掉水蛇特定的天數來通過，通過時間每條路徑有可能會不一樣。

水蛇的好友，袋鼠(Kangaroo)，希望可以挖出 N - M - 1 條新的路徑，讓水蛇可以在任意兩個水洞之間遊走。袋鼠可以在任意兩個水洞之間挖出新的路徑，而由袋鼠挖出的路徑，水蛇需要 L 天就可以通過。

另外，袋鼠希望水蛇在各水洞之間盡可能的快速移動。袋鼠將會挖出新的路徑，使得旅行於任兩個水洞之間所需要的時間最短。在袋鼠挖出新的路徑後，請你幫助水蛇和袋鼠計算出各水洞之間最長移動時間為何。


此為範例測資的圖。

Input:Output:

第一行有三個數字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

子任務分數額外輸入限制
114M = N - 2 ，每個水洞只連有一條或是兩條的初始路徑。換句話說，只存在著兩組的相連水洞，每組相連的水洞中不存在分岔的路徑。
210M = N ­ 2 和 N ≤ 100
323M = N ­ 2
418每個水洞至多連有一條初始路徑。
512N ≤ 3,000
623(無)
輸出一個數字，表示在袋鼠挖出新的路徑後所有水洞之間的最大的移動時間(如敘述)。

Sample Input:Sample Output:

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
18

HINT:


上圖展示了最終的路徑圖。最長的移動時間是從水洞0移動到水洞11，需18天。
這已經是最低所需時間—無論袋鼠怎麼改變挖路徑的方法，都會產生至少一組水洞使得水蛇需要花費18天以上(含)才能通過。

Source:

IOI 2013

Problem Setter

Testdata:

TestTimeMemoryScore
01000ms65536kb
1-11000ms65536kb14
1-21000ms65536kb
1-31000ms65536kb
1-41000ms65536kb
1-51000ms65536kb
1-61000ms65536kb
1-71000ms65536kb
1-81000ms65536kb
1-91000ms65536kb
1-101000ms65536kb
1-111000ms65536kb
1-121000ms65536kb
1-131000ms65536kb
2-11000ms65536kb10
2-21000ms65536kb
2-31000ms65536kb
2-41000ms65536kb
2-51000ms65536kb
2-61000ms65536kb
2-71000ms65536kb
2-81000ms65536kb
2-91000ms65536kb
2-101000ms65536kb
2-111000ms65536kb
2-121000ms65536kb
2-131000ms65536kb
2-141000ms65536kb
2-151000ms65536kb
2-161000ms65536kb
2-171000ms65536kb
2-181000ms65536kb
2-191000ms65536kb
2-201000ms65536kb
2-211000ms65536kb
2-221000ms65536kb
2-231000ms65536kb
2-241000ms65536kb
2-251000ms65536kb
3-11000ms65536kb23
3-21000ms65536kb
3-31000ms65536kb
3-41000ms65536kb
3-51000ms65536kb
3-61000ms65536kb
3-71000ms65536kb
3-81000ms65536kb
3-91000ms65536kb
3-101000ms65536kb
3-111000ms65536kb
3-121000ms65536kb
3-131000ms65536kb
3-141000ms65536kb
3-151000ms65536kb
3-161000ms65536kb
3-171000ms65536kb
3-181000ms65536kb
3-191000ms65536kb
3-201000ms65536kb
3-211000ms65536kb
3-221000ms65536kb
3-231000ms65536kb
3-241000ms65536kb
3-251000ms65536kb
4-11000ms65536kb18
4-21000ms65536kb
4-31000ms65536kb
4-41000ms65536kb
4-51000ms65536kb
4-61000ms65536kb
4-71000ms65536kb
4-81000ms65536kb
4-91000ms65536kb
4-101000ms65536kb
4-111000ms65536kb
4-121000ms65536kb
4-131000ms65536kb
4-141000ms65536kb
4-151000ms65536kb
4-161000ms65536kb
4-171000ms65536kb
4-181000ms65536kb
4-191000ms65536kb
4-201000ms65536kb
4-211000ms65536kb
4-221000ms65536kb
5-11000ms65536kb6
5-21000ms65536kb
5-31000ms65536kb
5-41000ms65536kb
5-51000ms65536kb
5-61000ms65536kb
5-71000ms65536kb
5-81000ms65536kb
5-91000ms65536kb
5-101000ms65536kb
5-111000ms65536kb
5-121000ms65536kb
5-131000ms65536kb
5-141000ms65536kb
5-151000ms65536kb
5-161000ms65536kb
5-171000ms65536kb
5-181000ms65536kb
5-191000ms65536kb
5-201000ms65536kb
5-211000ms65536kb
5-221000ms65536kb
5-231000ms65536kb
5-241000ms65536kb
5-251000ms65536kb
6-11000ms65536kb6
6-21000ms65536kb
6-31000ms65536kb
6-41000ms65536kb
6-51000ms65536kb
6-61000ms65536kb
6-71000ms65536kb
6-81000ms65536kb
6-91000ms65536kb
6-101000ms65536kb
6-111000ms65536kb
6-121000ms65536kb
6-131000ms65536kb
6-141000ms65536kb
6-151000ms65536kb
6-161000ms65536kb
6-171000ms65536kb
6-181000ms65536kb
6-191000ms65536kb
6-201000ms65536kb
6-211000ms65536kb
6-221000ms65536kb
7-11000ms65536kb11
7-21000ms65536kb
7-31000ms65536kb
7-41000ms65536kb
7-51000ms65536kb
7-61000ms65536kb
7-71000ms65536kb
7-81000ms65536kb
7-91000ms65536kb
7-101000ms65536kb
7-111000ms65536kb
7-121000ms65536kb
7-131000ms65536kb
7-141000ms65536kb
7-151000ms65536kb
7-161000ms65536kb
7-171000ms65536kb
7-181000ms65536kb
7-191000ms65536kb
7-201000ms65536kb
7-211000ms65536kb
7-221000ms65536kb
8-11000ms65536kb12
8-21000ms65536kb
8-31000ms65536kb
8-41000ms65536kb
8-51000ms65536kb
8-61000ms65536kb
8-71000ms65536kb
8-81000ms65536kb
8-91000ms65536kb
8-101000ms65536kb
8-111000ms65536kb
8-121000ms65536kb
8-131000ms65536kb
8-141000ms65536kb
8-151000ms65536kb
8-161000ms65536kb
8-171000ms65536kb
8-181000ms65536kb
8-191000ms65536kb
8-201000ms65536kb
8-211000ms65536kb

NeoHOJ — The new era of HOJ
頁面讀取時間: 0.0094 秒，使用記憶體: 0.55MB 。
GitHub