馬可和史拉可為了參加一年一度在克羅埃西亞矩形的雙人自行車馬拉松大賽正在加緊努力訓練。他們需要選擇一條路線來訓練。
在他們國家有N座程式與M條雙向道路。每一條道路連接兩個城市。但只有N-1條道路是已被鋪築好的，其他的道路則是還沒被鋪築好的道路，幸好任兩座城市間都有一條用以鋪築好的道路路徑所連接。換句話說，這N座城市與N-1條已被鋪築好的道路形成了一棵樹狀結構。
此外，每座城市最多可以是10條道路的端點。
訓練的路線可以從某一座城市開始，在經過數條道路後最後回到原來出發的城市。馬可和史拉可喜歡經過新的地點，所以他們定了一項規則就是絕不經過相同的城市且絕不騎過相同的道路。訓練的路線可以在任何一座城市開始並且不需要經過每一座城市。
騎乘在後座是輕鬆的，因為騎乘者可以因為前座騎乘者的關係而避開風。就因為如此，馬可和史拉可在每個城市會交換座位。為了確保他們能夠獲得相同的訓練量，他們想要選擇一條含有偶數條道路的路線。
馬可和史拉可的對手決定要封鎖某些尚未鋪築好的道路，讓他們無法找到一條滿足上述條件的路線。封鎖沒被鋪築好的道路需要付出一些代價(一個正整數)，而已被鋪築好的道路是不可能被封鎖的。
任務
寫一個程式，當給定城市與道路的描述後，找出封鎖道路使其無法滿足上述條件的訓練路徑之最小總代價。
輸入的第一行有兩個整數N與M (2 ≤ N ≤ 1 000, N−1 ≤ M ≤ 5 000)，分別代表城市的數目與道路的數目。
接下來的M行每一行都有三個整數A、B和C(1 ≤ A ≤ N, 1 ≤ B ≤ N, 0 ≤ C ≤ 10 000)，用來表示一條道路。A和B是不同的數字，表示直接由這條道路所連接的兩座城市。如果C=0，表示該道路已被鋪築好了；否則該道路是尚未被鋪築過，而C代表封鎖此一條道路所須付出的代價。
每座城市最多可以是10條道路的端點，且兩座城市間絕對不會有一條以上的道路直接連接。範例1 5 8 2 1 0 3 2 0 4 3 0 5 4 0 1 3 2 3 5 2 2 4 5 2 5 1 範例2 9 14 1 2 0 1 3 0 2 3 14 2 6 15 3 4 0 3 5 0 3 6 12 3 7 13 4 6 10 5 6 0 5 7 0 5 8 0 6 9 11 8 9 0
範例1 5 範例2 48
| 編號 | 身分 | 題目 | 主題 | 人氣 | 發表日期 |
|
沒有發現任何「解題報告」
|
|||||