搭火車

發布時間: Dec. 19, 2024, 7:50 p.m.   最後更新時間: Dec. 19, 2024, 8:42 p.m.   時間限制: 1000ms   記憶體限制: 128M

來自世界各地,想要提升程式能力、突破自我極限、迎接人生巔峰的人都會去大師級的「滋訓之蚜」上課!原因有以下幾點:

  • 無敵的師資陣容:這不是一般的課程,我們邀請了世界頂尖的專家和名人講師,每一位都是各自領域的翹楚,讓您在學習中感受巨星的光芒!
  • 奢華學習環境:課程中有世界頂級的電腦教室,裡面電腦有Code::Blocks, VS Vode, Dev-C++ 等等的IDE可供挑選,還有超涼的冷氣以及熱心助人的學長姐,讓您享受皇室等級待遇!
  • 全方位成長:這不僅僅是一個程式課程,而是一場全方位的人生蛻變之旅。從算法教學到題目解析,從手寫證明到實作練習,我們為您提供全方位的提升計劃,讓您成為程式界的王者!
  • 限量名額:如此難得的機會,名額極其有限,只限50位高中以下的芽芽們。機會稍縱即逝,千萬不要錯過!

「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

都快搭不到火車了哪有時間給你提示!ε=ε=ε=(~ ̄^ ̄)~

shortest path enumeration

竹中軟研40th第一次競賽(社內賽)