Restoring Road Network

AtCoder

IDarc083_b

Time2000ms

Memory256MB

Difficulty—

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}$ [samples]

Samples

Input #1

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.

Input #2

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.

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

Output #3

Input #4

3
0 1000000000 1000000000
1000000000 0 1000000000
1000000000 1000000000 0

Output #4

3000000000

API Response (JSON)

{
  "problem": {
    "name": "Restoring Road Network",
    "description": {
      "content": "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 be",
      "description_type": "Markdown"
    },
    "platform": "AtCoder",
    "limit": {
      "time_limit": 2000,
      "memory_limit": 262144
    },
    "difficulty": "None",
    "is_remote": true,
    "is_sync": true,
    "sync_url": null,
    "sign": "arc083_b"
  },
  "statements": [
    {
      "statement_type": "Markdown",
      "content": "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:\n\n*   People traveled be...",
      "is_translate": false,
      "language": "English"
    }
  ]
}

Full JSON Raw Segments