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

Problem : 260 - Race

Problem Statistics

Solved Member: 19　　Submission: 91　　User Tried: 20

Statement:

在 IOI 舉行的同時，Pattaya 城市也將舉辦一場賽車比賽：國際奧林匹亞賽車會（IOR）2011。身為主辦者，我們必須找出最佳的賽車比賽路線。

在這個Pattaya-Chonburi 都會區，有N-1 條公路連結N 個城市。每一條公路都是雙向、連接兩個不同城市，且其長度為一整數（單位為公里）。此外，對於任何兩個城市，都只有一個可能的連接路徑，也就是說，只有一條經由一連串不重複經過相同城市的公路路線，可以從一個城市連接到另一個城市。

IOR 有一個明確的規則：賽車路線的總長度必須為K 公里，且開始和結束必須在不同的城市。另外為了避免碰撞，在選定的路線上，沒有任何公路（所以也沒有任何城市）會被選兩次。為了將對交通的影響降至最低，賽車路線必須包含越少條公路越好。

Input:Output:

第一行有兩個整數N K，其中N表示城市的數目，城市編號從0 到 N-1，而K表示賽車比賽要求的距離。

第2行到第N行每行有三個數字u v L，表示公路連接城市 u 與城市 v，此公路的長度為 L。

Subtask 1 (9 points)
　•1 ≤ N ≤ 100
　•1 ≤ K ≤ 100
　•公路網為單純直線型態，給定0 ≤ i < N-1，公路i 連接城市i與城市i+1。

Subtask 2 (12 points)
　•1 ≤ N ≤ 1000
　•1 ≤ K ≤ 1000000

Subtask 3 (22 points)
　•1 ≤ N ≤ 200000
　•1 ≤ K ≤ 100

Subtask 4 (57 points)
　•1 ≤ N ≤ 200000
　•1 ≤ K ≤ 1000000
輸出長度恰為 K 的合法賽車路線中，所用到最少的公路數目。如果不存在這樣的路線輸出-1。

Sample Input:Sample Output:

Sample #1:
4 3
0 1 1
1 2 2
1 3 4

Sample #2:
3 3
0 1 1
1 2 1

Sample #3:
11 12
0 1 3
0 2 4
2 3 5
3 4 4
4 5 6
0 6 3
6 7 2
6 8 5
8 9 6
8 10 7
Sample #1:
2

Sample #2:
-1

Sample #3:
2

HINT:

　

Source:

IOI 2011

Problem Setter

Testdata:

TestTimeMemoryScore
0-11000ms262144kb
0-21000ms262144kb
0-31000ms262144kb
1-11000ms262144kb9
1-21000ms262144kb
1-31000ms262144kb
1-41000ms262144kb
1-51000ms262144kb
1-61000ms262144kb
1-71000ms262144kb
1-81000ms262144kb
1-91000ms262144kb
1-101000ms262144kb
1-111000ms262144kb
1-121000ms262144kb
1-131000ms262144kb
1-141000ms262144kb
1-151000ms262144kb
1-161000ms262144kb
1-171000ms262144kb
1-181000ms262144kb
2-13000ms262144kb12
2-23000ms262144kb
2-33000ms262144kb
2-43000ms262144kb
2-53000ms262144kb
2-63000ms262144kb
2-73000ms262144kb
2-83000ms262144kb
2-93000ms262144kb
2-103000ms262144kb
2-113000ms262144kb
2-123000ms262144kb
2-133000ms262144kb
2-143000ms262144kb
2-153000ms262144kb
2-163000ms262144kb
2-173000ms262144kb
2-183000ms262144kb
2-193000ms262144kb
2-203000ms262144kb
3-13000ms262144kb22
3-23000ms262144kb
3-33000ms262144kb
3-43000ms262144kb
3-53000ms262144kb
3-63000ms262144kb
3-73000ms262144kb
3-83000ms262144kb
3-93000ms262144kb
3-103000ms262144kb
3-113000ms262144kb
3-123000ms262144kb
3-133000ms262144kb
3-143000ms262144kb
3-153000ms262144kb
3-163000ms262144kb
4-13000ms262144kb57
4-23000ms262144kb
4-33000ms262144kb
4-43000ms262144kb
4-53000ms262144kb
4-63000ms262144kb
4-73000ms262144kb
4-83000ms262144kb
4-93000ms262144kb
4-103000ms262144kb
4-113000ms262144kb
4-123000ms262144kb
4-133000ms262144kb
4-143000ms262144kb
4-153000ms262144kb
4-163000ms262144kb

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