PM2.5的逆襲

View as PDF

Submit solution

Points: 100 (partial)
Time limit: 3.0s
Memory limit: 64M

Author:
Problem type


在20xx年,整個高雄市甚至是全台灣的空氣已經糟的無以復加,霧與霾已經無法互相辨認,
瀰漫著PM2.5的空氣使得人民足不出戶,希冀著有朝一日能重見光明。
就在人們對政府無法解決住環境的問題而抱怨時,
一位神通廣大的新秀科學家賈博士發明出了一種變形的過濾吸塵器,型態恍若一張巨網,透過靜電與改良過後的風扇而達到清淨空氣的效果。
於是政府決定先拿處於高雄中心的高雄中學來實驗。
一開始所有的道路都被PM2.5所覆蓋,污染值都是無限大,無法通行。
現在給予學校附近商家的數量與經過的天數,而機器每天都會選定\(x\) \(y\) \(d\)代表將\(x\)商家與\(y\)商家間的道路污染值控制在\(d\)。
因為你不喜歡去吃蝦米飯或者是咖喱屋的時候受到太多的污染,
所以你的任務是針對每天機器控制道路後,設計出一條連通這\(N\)個城市且途中總污染值最小的路徑(即路徑上能從任一點到另一點)
如果無法達成任務 請輸出"\\0w0//"(不含引號)


Input :
第一行包含一個整數\(T\),代表有幾筆測資
每筆測試資料中第一行包含二整數\(N, M\),代表\(N\)個地點與實施清潔計畫\(M\)天
接下來有\(M\)行,每行有三整數 \(x\) \(y\) \(d\) 代表將\(x\)商家與\(y\)商家間的道路污染值控制在\(d\)

Output :
針對每行輸入的道路控制訊息,輸出當天設計出的最小污染路徑污染值

HINT :

Sample input

1
4 4
1 2 3
2 3 4
3 4 5
1 3 2

Sample output

\\0w0//
\\0w0//
12
10

Comments

There are no comments at the moment.