100743: [AtCoder]ABC074 D - Restoring Road Network

Memory Limit:256 MB Time Limit:2 S
Judge Style:Text Compare Creator:
Submit:0 Solved:0

Description

Score : $500$ points

Problem Statement

In Takahashi Kingdom, which once existed, there are $N$ cities, and some pairs of cities are connected bidirectionally by roads. The following are known about the road network:

  • People traveled between cities only through roads. It was possible to reach any city from any other city, via intermediate cities if necessary.
  • Different roads may have had different lengths, but all the lengths were positive integers.

Snuke the archeologist found a table with $N$ rows and $N$ columns, $A$, in the ruin of Takahashi Kingdom. He thought that it represented the shortest distances between the cities along the roads in the kingdom.

Determine whether there exists a road network such that for each $u$ and $v$, the integer $A_{u, v}$ at the $u$-th row and $v$-th column of $A$ is equal to the length of the shortest path from City $u$ to City $v$. If such a network exist, find the shortest possible total length of the roads.

Constraints

  • $1 \leq N \leq 300$
  • If $i ≠ j$, $1 \leq A_{i, j} = A_{j, i} \leq 10^9$.
  • $A_{i, i} = 0$

Inputs

Input is given from Standard Input in the following format:

$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}$

Outputs

If there exists no network that satisfies the condition, print -1. If it exists, print the shortest possible total length of the roads.


Sample Input 1

3
0 1 3
1 0 2
3 2 0

Sample Output 1

3

The network below satisfies the condition:

  • City $1$ and City $2$ is connected by a road of length $1$.
  • City $2$ and City $3$ is connected by a road of length $2$.
  • City $3$ and City $1$ is not connected by a road.

Sample Input 2

3
0 1 3
1 0 1
3 1 0

Sample Output 2

-1

As there is a path of length $1$ from City $1$ to City $2$ and City $2$ to City $3$, there is a path of length $2$ from City $1$ to City $3$. However, according to the table, the shortest distance between City $1$ and City $3$ must be $3$.

Thus, we conclude that there exists no network that satisfies the condition.


Sample Input 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

Sample Output 3

82

Sample Input 4

3
0 1000000000 1000000000
1000000000 0 1000000000
1000000000 1000000000 0

Sample Output 4

3000000000

Input

题意翻译

#### 题面翻译 曾经存在的高桥王国有N个城市,城市与城市之间用长度为整数的无向道路连接。 现有一考古学家找到了一张N×N的表A,这张表代表了这N座城市两两之间的最短路。即表中的第u行第v列的值代表了从城市u到v的最短路长度。 问能否根据这张表,求出高桥王国的最小道路长度总和。 #### 输入格式 第一行:N 下面是大小为N×N的表A #### 输出格式 一个整数,表示最小道路长度总和。如果无解,输出−1 #### 数据范围与约定 - 1 <= N <= 300 - 当 i != j 时,1 <= 表A中第i行第j列的值 == 表A中第j行第i列的值 <= 10^9 - 表A中第i行第i列的值为0 #### 样例1解释 - 从城市1到城市2有长度为1的直接道路 - 从城市2到城市3有长度为2的直接道路 - 从城市1到城市3无直接道路 #### 样例2解释 从城市1走到城市2要走长度为1的道路,从城市2走到城市3要走长度为1的道路,所以从城市1到城市3要走的距离为2,但表中是3,所以无解。

加入题单

上一题 下一题 算法标签: