小傑是個高中生，在每年暑假期間都會來到他姑姑所經營的度假村裡義務地協助環境清潔作業。度假村中有 K 間小木屋（以整數 1, 2, ..., K 來編號每間小木屋），而任兩間小木屋之間可能會有 1 條小路直接連結（此小路的中間不會有岔路連到其他的小木屋），或者可以透過 2條（含）以上的小路間接連結（如下圖所示）。
這些小路上常會留有旅客們不小心散落的許多堆的垃圾（假設每一堆垃圾都為 1 公斤），其重量總和為若干公斤重（為整數值）。
小傑的任務為從編號為 1 的小木屋（即小木屋 1）開始進行環境清潔作業，隨意地選擇一條這間小木屋可以連出的小路出發走向另一間小木屋（不可以中途折返），將在沿此路行走時所看到四處散落的垃圾收集到隨身的一個暫存容器內（最多可存放 M 公斤重的垃圾，M 假設為整數），然後到達下一間小木屋後將之傾倒在一個很大的垃圾桶內（每一間小木屋都有）讓暫存容器清空，再任意地選擇一條目前這間小木屋可以連出的小路出發來繼續進行相同的垃圾收集作業（走過的小路可以重複行走以便清除路上可能還剩餘的垃圾）。
假設小傑行走在每一條小路的進行時間都是固定為 1 個單位時間（不管有沒有垃圾存在），並且其他的作業時間不計。請問在總作業的時間最多為 N 個單位時間的限制下，小傑最多可以清除的垃圾總共為幾公斤？
第一行有 4 個整數 K(1 ≤ K ≤ 50)、M(1 ≤ M ≤ 10)、 N(1 ≤ N ≤ 1,000)、 P(1 ≤ P ≤ K(K-1)/2)，以空格間隔；
它們分別代表小木屋數目、小明隨身暫存容器的容量(單位是公斤)、總作業時間、以及連接小木屋的小路數目。
第二行開始總共有 P 行，每行表示一條小路的資訊，共有 3 個整數；
前 2 個正整數代表此小路所連接兩間小木屋的編號(編號小的在前)，
最後 1 個整數是此小路上散落的垃圾重量和(其值為 0 到 100 間的整數)。
為一個整數值，代表小傑最多可以清除垃圾的公斤數。
範例輸入一： 4 1 50 4 1 2 2 1 3 0 2 3 3 3 4 10 範例輸入二： 4 2 7 4 1 2 1 1 3 3 2 3 0 3 4 20
範例輸出一： 15 範例輸出二： 14
| 編號 | 身分 | 題目 | 主題 | 人氣 | 發表日期 |
|
沒有發現任何「解題報告」
|
|||||