c812. 1. 觀光景點
Tags :
Accepted rate : 580人/611人 ( 95% ) [非即時]
評分方式:
Tolerant

最近更新 : 2021-03-26 12:39

Content

打卡公司為了促進城市觀光,發展一個可推薦前往觀光(打卡)的App。該公司選定了 N 個觀光(打卡)點,若遊客在任一觀光點打卡,該App就會預測遊客可能會有興趣的其他觀光點並推薦給該遊客。

為了能夠準確預測該推薦的觀光點,打卡公司設計了觀光景點相關性地圖(如下圖),圖上有 N 個點,分別以 V1, V2, V3, …, VN 代表觀光點,並精心挑選了 N−1 組觀光點以線段相連並依據經驗給定 Ri,j 值,以代表 Vi 與 Vj 的相關性。特別的是,該圖之任意兩點 Vm 與 Vn 一定有單一路徑 p ,相互串連,而Vm 與 Vn 的相關性就為該路徑上所有已知相關性的最小值 (即路徑上最小Ri,j值)。以下圖為例 V1 與 V2的相關性為 min {4, 3, 6} = 3。

請寫一個程式計算與任一觀光點 Vk 相關性至少為 q 的景點數量。

Input

輸入的第一行有三個以空白符號隔開的正整數 N, Vk, q。接著 N-1 行中,每一行有三個空白符號隔開的正整數分別代表 i, j, Ri,j。保證1 ≤ i ≤ N、1 ≤ j ≤ N、q≤109、Ri,j ≤ 109

Output

請輸出與觀光點 Vk 相關性不低於 q 的景點數量。

Sample Input #1
3 2 4
1 2 3
1 3 2
Sample Output #1
0
Sample Input #2
6 4 6
4 2 10
3 6 3
5 3 8
2 3 6
1 6 4
Sample Output #2
3
測資資訊:
記憶體限制: 512 MB
公開 測資點#0 (14%): 1.0s , <1K
公開 測資點#1 (1%): 1.0s , <1K
公開 測資點#2 (1%): 1.0s , <1K
公開 測資點#3 (1%): 1.0s , <1K
公開 測資點#4 (1%): 1.0s , <1K
公開 測資點#5 (30%): 1.0s , <1K
公開 測資點#6 (1%): 1.0s , <1K
公開 測資點#7 (1%): 1.0s , <1K
公開 測資點#8 (1%): 1.0s , <1K
公開 測資點#9 (1%): 1.0s , <1K
公開 測資點#10 (1%): 1.0s , <1K
公開 測資點#11 (1%): 1.0s , <1K
公開 測資點#12 (23%): 1.0s , <1K
公開 測資點#13 (1%): 1.0s , <1K
公開 測資點#14 (1%): 1.0s , <1K
公開 測資點#15 (1%): 1.0s , <1K
公開 測資點#16 (1%): 1.0s , <1K
公開 測資點#17 (1%): 1.0s , <1K
公開 測資點#18 (1%): 1.0s , <1K
公開 測資點#19 (2%): 1.0s , <1M
公開 測資點#20 (1%): 1.0s , <1M
公開 測資點#21 (1%): 1.0s , <1M
公開 測資點#22 (1%): 1.0s , <1M
公開 測資點#23 (1%): 1.0s , <1M
公開 測資點#24 (1%): 1.0s , <1M
公開 測資點#25 (1%): 1.0s , <1M
公開 測資點#26 (1%): 1.0s , <1M
公開 測資點#27 (1%): 1.0s , <1M
公開 測資點#28 (1%): 1.0s , <1M
公開 測資點#29 (1%): 1.0s , <1M
公開 測資點#30 (1%): 1.0s , <1M
公開 測資點#31 (1%): 1.0s , <1M
公開 測資點#32 (1%): 1.0s , <1M
公開 測資點#33 (1%): 1.0s , <1M
公開 測資點#34 (1%): 1.0s , <1M
Hint :

本題共有四個子題。第一子題N = 4,全對得18分。第二子題N ≤ 10,全對得36分。第三子題 N ≤ 50,全對得29分。第四子題 N ≤ 5,000,全對得17分。

Tags:
出處:
107學年度全國資訊學科能力競賽 [管理者: icube (!@#$%^&*()_...) ]

Status Forum 排行

ID User Problem Subject Hit Post Date
38423 qerpzzea@gma ... (賽希爾 cecill(陳宥穎)) c812
思路
249 2023-11-21 20:24
24787 kevin2002062 ... (欣倫李) c812
被騙了
1201 2021-03-25 18:09