Problem1286--PIPI运货

1286: PIPI运货

Time Limit: 1 Sec  Memory Limit: 128 MB
Submit: 643  Solved: 305
[Submit] [Status] [Web Board] [Creator:]

Description

PIPI是一个商人,经常需要将货物从A地运到B地,我们可以把PIPI经常活动的区域抽象成一个n个结点的地图,用一个nxn的矩阵表示。
矩阵第i行第j列的值代表PIPI从 i 地将货物运到 j 地所需要的固定费用,若该值为-1则代表 i 和 j之间没有直接的通路,注意道路是双向的。
除了上述固定费用外,PIPI在经过每一个结点时都需要交一次过路费(起点和终点不需要交过路费)。
作为一个精打细算的商人,你能帮PIPI计算出从A地到B地的最少费用是多少吗?

Input

第一行输入结点数目n (0<n<=100)
接下来n行输入一个nxn的矩阵(矩阵的值不大于1000)。
第n+2行输入n个数,代表每个结点的过路费cost(cost<=1000)。
第n+3行输入一个数q (q<=10000),代表PIPI的询问次数。
接下来q行,每行输入两个数字,询问A到B的最少花费。

Output

输出q个数字,代表q次询问的结果。若询问的两个地点不可达,输出-1.

Sample Input

5
0 3 22 -1 4
3 0 5 -1 -1
22 5 0 9 20
-1 -1 9 0 4
4 -1 20 4 0
5 17 8 3 1
3
1 3
3 5
2 4

Sample Output

21
16
17

Source/Category