1685 . 阿思歐思 Asterix and Obelix
Description
阿思(Asterix)和他的摯友歐思(Obelix)在遙遠的地方打贏了一場對抗羅馬人的艱鉅戰鬥後踏上了回程。
然而，歐思現在沒有和阿思在一起。他為了要運送大大大大石頭(menhir)給某位他的網路買家而離開了阿思。
(或許你知道歐思的事業漸漸拓展，已經延伸到網路上了。)
不過歐思答應要和阿思在回家途中會合，阿思也承諾在他們會面的城市請歐思一頓大餐(你也知道歐思多胖！)。
阿思和歐思可以在任何城市會面，包括起點和終點。
現在阿思正坐著看地圖，試著找出一條最便宜的路徑。
地圖上標示著所有城市還有連接兩座城市的雙向道所需的旅費(單位是Sestertii，古羅馬貨幣單位)。
每座城市還有計算出在該座城市吃大餐的費用(單位還是Sestertii)。
阿思只會在一座城市請歐思吃大餐，而且該座城市會是整條道路中費用最高的城市。
由於阿思沒有電腦，請你寫一個城市幫他計算出最便宜路徑的花費。
Input Format
單一輸入檔案包含多筆測試資料。
第一行包含三個數字C <= 200, R <= 10000, 以及Q < = 10000。
C表示城市的數目，編號1~C、R表示道路的數目以及Q表示詢問數。
接下來會有一行有著C個數字依序表示每座城市吃大餐的花費。(保證是正整數)
再來有R行，每行有三個數字，C1,C2,D，表示有一條連接C1和C2(保證C1≠C2)的雙向道路，旅費是D(保證是正整數)
再來會有Q行每行兩個數字CS,CT(保證CS≠CT)，表示要求出從CS到CT的最便宜路徑的費用。
C=R=Q=0時輸入結束，請不要對這行進行任何輸出。
Output Format
對每筆測試資料先輸出Case Number(從1開始)。
接下來對每筆詢問輸出一行表示最省錢的路徑花費。
如果兩座城市之間不可到達，請輸出-1。
在兩筆測試資料間輸出一個空白行。
Sample Input 1
2 3 5 15 4 4 6
1 2 20
1 4 20
1 5 50
2 3 10
3 4 10
3 5 10
4 5 15
6 7 10
1 5
1 6
5 1
3 1
6 7
4 4 2
2 1 8 3
1 2 7
1 3 5
2 4 8
3 4 6
1 4
2 3
0 0 0
Sample Output 1
45
-1
45
35
16
Case #2
18
20
Hints
保證所有運算不會超過int範圍。
Problem Source
原TIOJ1685 / UVa 10246 (測資範圍加大)
Subtasks
| No. | Testdata Range | Score |
|---|---|---|
| 1 | 0 | 100 |