2021 年世界末日，全球爆發恐怖的喪屍病毒，小帥與女朋友分隔兩地，被困在各自的家中，因為擔心女朋友的安全，小帥想要用最短的時間去找女朋友，並帶著她回到自己家中，由於小帥在街上奔跑，會引起許多喪屍的注意。因此，當小帥找到女友之後，就必須要選擇一條完全不同的路徑返回家中（當然他也有可能會穿過相同的十字路口），不然兩人都會有生命危險。
再次提醒，小帥兩人返家時，之前經過的任何一條街道都不能重複再走，許多喪屍們可能在那裡附近遊蕩，等著飽餐一頓。
而如果可以順利帶著女友返回家中，這段路程需要耗費的最短時間為何？
舉例來說，小帥家位於起點 $1$，女友家位於終點 $4$，小帥可以走路線 [$1$, $2$, $4$]，由於需要選擇一條完全不同的路徑返家，所以小帥回程應該要走路線[4, 3, 1]，因此得到這段路程需耗費的最短時間為 $202$ 分。
然而，小帥也有可能沒辦法找到完全避開喪屍的路徑返家，小帥就只能待在女友家了。
舉例來說，小帥家位於起點 $1$，女友家位於終點 $9$，小帥可以走路線 [$1$, $2$, $5$, $7$, $9$]，但是小帥回程找不到一條完全不同的路徑返家，因此這段路程需耗費的最短時間為 $40$ 分。
1) 第一行為一正整數 $n$，正整數 $n$ ($2\leq n\leq 100$) 代表節點數。比如小帥家就是在第 $1$ 號節點，女友家就是在第 $n$ 號節點。
2) 第二行為一正整數 $m$，正整數 $m$ 代表街道數量，所以接下來的 $m$ 行將描述 $m$ 條街道。
3) 接下來每行將包含 $3$ 個正整數，由街道連接的兩個節點和走完該街道所需的時間（以分為單位）。而任何街道都不會讓人走超過 $1000$ 分或短於 $1$ 分。
4) 任意兩節點間都存在路徑連通。
5) 每條街道將連接兩個不同的節點，且一對節點只能連接一條街道。
1) 輸出一個正整數，這個正整數是小帥接到女友後返回自家所需的最短時間。
2) 如果路線完全沒有辦法避開喪屍，請輸出小帥跑到女友家的最短時間。
4 5 1 2 1 1 3 99 2 3 2 2 4 99 3 4 3
202
9 12 1 2 10 1 3 10 1 4 10 2 5 10 3 5 10 5 4 10 5 7 10 6 7 10 6 9 10 7 8 10 7 9 10 8 9 10
40
| 編號 | 身分 | 題目 | 主題 | 人氣 | 發表日期 |
|
沒有發現任何「解題報告」
|
|||||