(劇情接續 a773)
在離開原本的世界後，tree 和 revival 來到了一個大迷宮。
進入迷宮後不久，他們看到一塊告示牌：
「此迷宮由偉大的魔法師 william 所建造，迷宮中分成不同區塊，每個區塊都有若干項通關信物，
為了方便管理，每區的通關信物都會放在同個箱子裡，而每個信物上也都有附上魔法，
它會說明下個信物該到哪裡尋找，並且形狀如何，讓你在每個區塊的信物箱中不會搞錯該拿哪一個信物。
當然，整塊大迷宮也都有附上魔法，不管是走得快或是走得慢的人，運氣好的或運氣壞的人，
從迷宮一個區塊到另一個區塊所花費時間都是相同的，各位挑戰迷宮的王者阿，如果要破解迷宮，請 $2$ 人一起同行，
利用最短的時間，依序拿到所有通關信物，回到起點大門前，william 將在門口等著兩位勝者的歸來。
有問題可以對此告示牌發問。」
tree：「太多吐槽點了吧......有些地方搞得很像正常人講話，有些地方又很中二阿......而且可以發問是怎樣啦！」
revival：「告示牌，我有問題。兩人同行是要一起走還是分開啊？」
告示牌顯現出新的文字：「在一人行動時，另一位將會因魔法而被困在當地。」
revival：「這是分開行動的意思吧......那要怎麼做才算依序拿到通關信物啊？或許前一個信物是 tree 拿的，但我可能離下個信物比較近啊？」
告示牌：「只要依照時序拿到通關信物即可，誰拿的都沒關係。」
revival：「那假設我今天拿到通關信物，我會知道下一個通關信物在哪，可是 tree 要怎麼知道？可能他離下個信物比較近啊！」
告示牌：「你問的東西太多了。」
revival：「......這甚麼告示牌啦！」
tree：「那假設我今天拿到通關信物，我會知道下一個通關信物在哪，可是 revival 要怎麼知道？可能他離下個信物比較近啊！」
告示牌：「拿到通關信物後，下個信物的資訊將會顯現在兩人的手上。」
revival：「tree 你小心點，你剩一次發問......」
tree：「那有沒有從迷宮一塊走到另一塊需要花費多久的資訊？還有信物順序到底是甚麼？」
告示牌：「終於有懂發問的人了......如此即可在開始收集信物前想好所有的收集路線！以下顯示您剛才需要吾提供之資訊，祝您闖關順利。」
tree：「雖然他講話方式真的很怪，但至少我們拿到有用的東西了。」
revival：「趕快規劃路線趕快攻略迷宮，我還想回去地球啦！」
tree：「對欸，我忘記我們在類似異世界的地方了，趕快回去~」
第一行輸入兩正整數 $n,\;k$，
代表迷宮有 $n$ 個區塊 (編號為 $1\sim n$)、
告示牌告訴 tree $k$ 條路線資訊。
接下來 $k$ 行，每行有三正整數 $u_i,\;w_i,\;t_i$，
代表從第 $u_i$ 塊迷宮走到第 $w_i$ 塊迷宮需花費 $t_i$ 時間。
以上路線皆為雙向路，且輸入保證迷宮連通。
第 $k+2$ 行，輸入一正整數 $p$，代表有 $p$ 項通關信物需要收集。
第 $k+3$ 行，有 $p$ 個正整數 $a_j$，代表第 $j$ 項通關信物在迷宮第 $a_j$ 區塊。
輸出一數，代表 tree 和 revival 最少需要花費多少時間攻略迷宮並回到起點見偉大的魔法師 william。
5 6 1 2 2 2 3 1 1 3 4 5 3 1 3 4 1 2 4 3 5 3 2 4 1 4
10
起點和告示牌都在第 $1$ 區。
$30\%$ 測資，$p \leq 20$
$30\%$ 測資，$k = n-1$
$40\%$ 測資，無特別限制
對於所有測資，$n\leq 100,\;n-1\leq k\leq\frac{n(n - 1)}{2},\;p\leq 10^4,\;t_i\leq 100,\;1\leq u_i,\;w_i,\;a_j\leq n$
範例測資中，revival 從第 $1$ 區經過 $2$ 區得到第 $3$ 區信物，再走到第 $2$ 區拿信物，
再經過 $3$ 區到第 $4$ 區拿信物，接下來 tree 直接在第 $1$ 區拿信物(花費時間為 $0$)，而 revival 也在第 $4$ 區得到最後一個信物。
最後，tree 和 revival 回到第 $1$ 區見 william (其實 tree 就待在原地，一樣耗費 $0$ 時間)，整段過程共耗費 $10$ 單位時間。
| 編號 | 身分 | 題目 | 主題 | 人氣 | 發表日期 |
沒有發現任何「解題報告」 |
|||||