分数: 500 点
问题陈述
在曾经存在的高桥王国里,有 N 城市,并且某些城市对通过道路双向连接。 有关道路网络的已知信息如下:
- 人们仅通过道路在城市之间出行。如有必要,可以通过中间城市从任何其他城市到达任何城市。
- 不同的道路可能有不同的长度,但所有长度都是正整数。
考古学家潜伏发现了一张桌子 N 行和 N 列, A,高桥王国废墟中。 他认为这代表了王国沿路各城市之间的最短距离。
确定是否存在一个道路网络,使得对于每个 u 和 v,整数 A_{u, v} 在 u第行和 v第列 A 等于从 City 出发的最短路径的长度 u 前往城市 v。 如果存在这样的网络,请找到尽可能短的道路总长度。
约束
- 1 \leq N \leq 300
- If i ≠ j, 1 \leq A_{i, j} = A_{j, i} \leq 10^9.
- A_{i, i} = 0
输入
输入由标准输入按以下格式给出:
N
A_{1, 1} A_{1, 2} ... A_{1, N}
A_{2, 1} A_{2, 2} ... A_{2, N}
...
A_{N, 1} A_{N, 2} ... A_{N, N}
输出
如果不存在满足条件的网络,则打印 -1。
如果存在,请打印尽可能短的道路总长度。
示例输入 1
3 0 1 3 1 0 2 3 2 0
示例输出 1
3
以下网络满足条件:
- 城市 1 和城市 2 由一条很长的路连接 1.
- 城市 2 和城市 3 由一条很长的路连接 2.
- 城市 3 和城市 1 没有道路连接。
示例输入 2
3 0 1 3 1 0 1 3 1 0
示例输出 2
-1
因为有一条长度的路径 1 来自城市 1 前往城市 2 和城市 2 前往城市 3,有一条长度为 2 来自城市 1 前往城市 3。 但根据表,城市之间的最短距离 1 和城市 3 必须是 3.
因此,我们得出结论,不存在满足条件的网络。
示例输入 3
5 0 21 18 11 28 21 0 13 10 26 18 13 0 23 13 11 10 23 0 17 28 26 13 17 0
示例输出 3
82
示例输入 4
3 0 1000000000 1000000000 1000000000 0 1000000000 1000000000 1000000000 0
示例输出 4
3000000000