發布時間: Dec. 19, 2024, 7:50 p.m. 最後更新時間: Dec. 19, 2024, 8:42 p.m. 時間限制: 1000ms 記憶體限制: 128M
來自世界各地,想要提升程式能力、突破自我極限、迎接人生巔峰的人都會去大師級的「滋訓之蚜」上課!原因有以下幾點:
「Wow!」
「這東東太讚了!我好想去啊......」這時,hush忽然眼睛一亮「ㄟˊ?這東西竟然新竹也有!我一定要去報名!」
(つ≧▽≦)つ
.
.
.
「什麼!?你說竹區的班沒開成?」(ノಥ,_」ಥ)ノ彡┻━┻
「天啊!那我只好每個禮拜去台北上課了QQ......」突然的噩耗讓hush感到非常傷心。
於是,hush展開了一個多學期的通勤之旅。
台灣在日治時期就發展出縱貫的火車鐵路,讓長途旅行的人可以不用走路就到達目的地,蒸蚌。於是火車這種俗擱大碗的交通工具自然成為窮人hush的首選。不過魷魚他放學都在教室裡蹭冷氣蹭到有點晚,然後星期六晚上又常常有事情,這造成他常常需要趕火車
.·´¯\`(>▂<)´¯\`·.
「啊啊啊怎麼已經17:19了!!!!!」hush又在驚慌失措的大叫。
快點快點,快要趕不上17:32的1231號列車了,從德田館到臺北車站的曼哈頓距離大約5120212mm!附近有$n-2$個路口(編號為$2$~$n-1$),$m$條道路(皆可以雙向奔赴),每條道路的距離不會是負的(不讓hush偷距離QAQ),好險hush學會了瞬移技能(讓那條路當下的距離變$0$)好讓他不會遲到,不過一天只能選擇一條路瞬移,快幫他他算出德田館到北車的最短距離不然他就要出事囉!(德田館和北車外的路口編號分別為$1,n$)
第一行給你兩個整數$n,m$,代表有$n$個路口和$m$條道路
接下來$m$行每行給你三個整數$u$ $v$ $w$代表路口$u$與路口$v$的距離為$w$
($2\le n\le 10^4, 1\le m\le 10^5$)
($u,v\in [1,n], w\in [1,10^9]$)
輸出一行整數代表hush路口$1$到路口$n$的最短距離
8 10 1 5 2 4 3 1 7 8 10 3 1 5 8 4 10 7 8 2 5 1 9 3 1 3 3 5 4 8 4 8
4