c812. 1. 觀光景點 - 高中生程式解題系統

內容

打卡公司為了促進城市觀光，發展一個可推薦前往觀光(打卡)的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 的景點數量。

輸入說明

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

輸出說明

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

範例輸入 #1

3 2 4
1 2 3
1 3 2

範例輸出 #1

範例輸入 #2

範例輸出 #2

測資資訊：

記憶體限制： 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

提示：

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

標籤:

出處:

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

編號	身分	題目	主題	人氣	發表日期
38423	qerpzzea@gma ... (賽希爾 cecill(陳宥穎))	c812	思路	128	2023-11-21 20:24
24787	kevin2002062 ... (欣倫李)	c812	被騙了	1096	2021-03-25 18:09