题目描述

设 $G$ 为一个带权图，即图 $G$ 中的每条边都关联一个非负整数权重。一条路径的长度是该路径上各边权重之和。图 $G$ 中顶点 $r$ 和 $s$ 之间的最短路径，记为 $P_G(r, s)$，定义为从 $r$ 到 $s$ 长度最短的路径。顶点 $r$ 和 $s$ 之间的距离，记为 $d_G(r, s)$，是最短路径 $P_G(r, s)$ 的长度。对于连通图中的两个顶点，它们之间至少存在一条最短路径。设 $e = (u, v)$ 是 $P_G(r, s)$ 中的一条边，且 $v$ 比 $u$ 更靠近 $s$（$v$ 可能等于 $s$）。设 $G - e$ 表示从图 $G$ 中移除边 $e$ 后得到的子图。从 $u$ 出发的迂回路径是指在 $G - e$ 中从 $u$ 到 $s$ 的最短路径，即 $P_{G - e}(u, s)$。如果移除边 $e$ 会导致从 $u$ 到 $s$ 的距离增加最大，那么边 $e$ 就是 $P_G(r, s)$ 中的迂回关键边。换句话说，如果 $e$ 是 $P_G(r, s)$ 中的迂回关键边，那么在 $P_G(r, s)$ 的所有边中，$d_{G - e}(u, s) - d_G(u, s)$ 的值最大。最长迂回路径问题就是要找出最短路径的最大距离增量。

图 4：一个带权图 $G$

例如，如图 4 所示。$P_G(4, 1) = \langle 4, 3, 2, 1 \rangle$ 是从顶点 $4$ 到顶点 $1$ 的最短路径。如果移除边 $(4, 3)$，路径 $\langle 4, 6, 1 \rangle$ 就是从顶点 $4$ 到顶点 $1$ 的迂回路径。如果移除边 $(3, 2)$，路径 $\langle 3, 5, 1 \rangle$ 就是从顶点 $3$ 到顶点 $1$ 的迂回路径。如果移除边 $(2, 1)$，路径 $\langle 2, 5, 1 \rangle$ 就是从顶点 $2$ 到顶点 $1$ 的迂回路径。$P_G(4, 1)$ 中的迂回关键边不是边 $(4, 3)$ 也不是边 $(2, 1)$，而是边 $(3, 2)$，因为 $d_{G - (3, 2)}(3, 1) - d_G(3, 1) = 600 - 200 = 400$，大于 $d_{G - (4, 3)}(4, 1) - d_G(4, 1) = 500 - 300 = 200$ 以及 $d_{G - (2, 1)}(2, 1) - d_G(2, 1) = 200 - 100 = 100$。

从网络管理的角度来看，寻找迂回路径以及确定迂回关键边的算法非常重要。由于某个顶点处的边突然失效，消息必须通过与故障边相邻顶点的迂回路径重新传输。

假设我们有多个网络。每个网络都是连通的，且最多包含 $n$ 个顶点，其中 $3 \leq n \leq 100$。现在假设你受聘担任网络管理员，需要为每个网络确定给定最短路径的迂回关键边所导致的最大距离增量。

输入

输入包含多个测试用例。第一行包含一个整数，表示测试用例的数量。每个测试用例以一个正整数 $n$ 开始，其中 $3 \leq n \leq 100$。接下来的 $n$ 行表示一个网络的邻接矩阵。具有 $n$ 个顶点的网络 $G$ 的邻接矩阵，记为 $A(G) = [w_{u, v}]$，是一个 $n \times n$ 的矩阵，若 $(u, v)$ 是图 $G$ 的一条边，则 $w_{u, v} > 0$；否则，$w_{u, v} = 0$，其中 $w_{u, v}$ 是一个非负整数。注意，邻接矩阵每行中的任意两个元素之间用一个空格分隔。每个测试用例的最后一行表示给定最短路径中的顶点序列，其中两个顶点之间也用一个空格分隔。注意，第一个和最后一个顶点分别表示源顶点和目标顶点。例如，图 4 中图形的邻接矩阵在示例输入的测试用例 3 中给出。

输出

对于每个测试用例，在一行中输出给定最短路径的迂回关键边所导致的最大距离增量。

输入样例

3
3
0 10 20
10 0 10
20 10 0
3 2 1
4
0 10 10 30
10 0 30 0
10 30 0 10
30 0 10 0
4 3 1 2
6
0 100 0 0 100 200
100 0 100 0 100 400
0 100 0 100 500 0
0 0 100 0 500 300
100 100 500 500 0 0
200 400 0 300 0 0
4 3 2 1

输出样例

20
30
400

题目来源

台湾 2002 年竞赛题目