1659: 最小运输费用

在春城之国里，一共有N个城市。在两个城市之间只有一条运输道路，或者根本没有道路。现在有一辆货车要从一个城市开往另一个城市。但是这个运输费用包括下面的两部分：
1.在两个城市之间运输公路上的费用，汽油等；
2.要交纳的税，因为货车每经过一个城市都要向这个城市交纳一定的税务。但是始发城市和目的城市用不着缴纳税务。

你要编写一个程序，来选择一条运输费用最小的路线。

输入文件的第一行是一个正整数N（1≤N≤50），接下来N行，每行N个整数，为在两个城市的道路上消耗的费用；下面的一行有N个整数，每个整数为向城市缴纳的税务；后面的每一行有两个整数，表示始发城市和目的城市。具体输入格式为：

A₁₁  A₁₂ … A_1N

A₂₁  A₂₂ … A_2N

…   …  …  …

A_N1  A_N2 … A_NN

B₁  B₂ … B_N

C  D

E  F

… …

G  H

其中Aij就是从城市i到城市j的运输费用，当Aij = -1时就意味着这两个城市之间没有公路；Bi为经过城市i所要缴纳的税务。这里要一辆货车从城市C发往城市D，要一辆货车从城市E发往城市F，……，要一辆货车从城市G发往城市H。

输出文件的内容要包括从哪个城市到达哪个城市；所选择的路线和总共的运输费用。

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
1 3
3 5
2 4

From 1 to 3:
Path: 1->5->4->3
Total: 21

From 3 to 5:
Path: 3->4->5
Total: 16

From 2 to 4:
Path: 2->1->5->4
Total: 17