c812. 1. 觀光景點
標籤 :
通過比率 : 588人/619人 ( 95% ) [非即時]
評分方式:
Tolerant

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

內容

打卡公司為了促進城市觀光,發展一個可推薦前往觀光(打卡)的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≤109、Ri,j ≤ 109

輸出說明

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

範例輸入 #1
3 2 4
1 2 3
1 3 2
範例輸出 #1
0
範例輸入 #2
6 4 6
4 2 10
3 6 3
5 3 8
2 3 6
1 6 4
範例輸出 #2
3
測資資訊:
記憶體限制: 512 MB
提示 :

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

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

本題狀況 本題討論 排行

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