回分類題庫
c055: 6.超級大轉機
關鍵字: 109校內初賽

測資點 : 10 | Time Limit : 1000 ms | Memory Limit : 32000 KB
Accepted : 45 Times / 34 Users | Submit : 304 Times / 55 Users | Accepted rate : 62%
題目加入時間 : 2020-08-03 17:35

Content: 简体中文

還記得去年的「轉機」和「大轉機」嗎?今年Sagit要挑戰去更遠的地方,而且這些地方可能要透過更多的轉機點來轉機,而且每個轉機點要收取不同的轉機費用。

Sagit看著所有航線的資料,想找出一條最便宜的轉機方式,不過由於轉機點的資料太多,Sagit的頭腦已經無法思考,你能幫他找出這條最便宜的轉機方式要花多少錢嗎? 

Input:

輸入資料第一行有一個正整數 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。另外,兩點之間可能不只有一條航班。

Output:

請輸出從第1點到第N點所花的費用最少為多少。如果依照所給的資料,無法從第1點到達第N點,則請輸出-1。

Sample Input:help

若題目沒有特別說明,則應該以多測資的方式讀取,若不知如何讀取請參考 a001 的範例程式。
輸入1:
3
0 1 0
2
1 2 1
2 3 1

輸入2:
5
0 1 1 1 0
2
1 2 1
4 5 1

Sample Output :

輸出1:
3

輸出2:
-1

Hint :

Author :

109校內初賽 (管理員:sagit)

  Solve it!   Status Forum