還記得去年的「轉機」和「大轉機」嗎？今年Sagit要挑戰去更遠的地方，而且這些地方可能要透過更多的轉機點來轉機，而且每個轉機點要收取不同的轉機費用。
Sagit看著所有航線的資料，想找出一條最便宜的轉機方式，不過由於轉機點的資料太多，Sagit的頭腦已經無法思考，你能幫他找出這條最便宜的轉機方式要花多少錢嗎？
輸入資料第一行有一個正整數 N (3<=N<=500)，代表包括起點、終點以及所有的轉機點。
第二行有 N 個 0~10000 的正整數，代表通過這些轉機點轉機時要收取的費用，其中第1點是起點，第N點是終點，這兩點因為不是轉機，所以固定為 0。
第三行有一個正整數 M (2<=M<=N2)，代表接下來有幾條航班的資訊。
接下來 M 行，每行有三個正整數 A、B、K (1<=A、B<=N，0<=K<=100000)，代表 A、B 兩點之間有一個航班，其費用為 K。另外，兩點之間可能不只有一條航班。
請輸出從第1點到第N點所花的費用最少為多少。如果依照所給的資料，無法從第1點到達第N點，則請輸出-1。
3 0 1 0 2 1 2 1 2 3 1
3
5 0 1 1 1 0 2 1 2 1 4 5 1
-1
| 編號 | 身分 | 題目 | 主題 | 人氣 | 發表日期 |
沒有發現任何「解題報告」 |
|||||