← 返回题目列表

AtCoder · arc083_b

D. 恢复路网

中文机器翻译题面 查看原题

分数: 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