TopCoder

User's AC Ratio

80.0% (4/5)

Submission's AC Ratio

26.1% (6/23)

Tags

uva

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

7 8 5
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

Case #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

Testdata and Limits

No. Time Limit (ms) Memory Limit (KiB) Output Limit (KiB) Subtasks
0 2000 65536 262144 1