Restoring Road Network

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 Au,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≤N≤300
• If i≠j, 1≤Ai,j=Aj,i≤109.
• Ai,i=0

NA1,1 A1,2 … A1,NA2,1 A2,2 … A2,N…AN,1 AN,2 … AN,N

Sample Input 1

30 1 31 0 23 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

30 1 31 0 13 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

50 21 18 11 2821 0 13 10 2618 13 0 23 1311 10 23 0 1728 26 13 17 0

Sample Output 3

82

Sample Input 4

30 1000000000 10000000001000000000 0 10000000001000000000 1000000000 0

 1 #include<bits/stdc++.h> 2 using namespace std; 3 #define LL long long 4 #define eps 1e-8 5 #define MX 305 6 ?7 int n; 8 int G[MX][MX]; 9 10 int main()11 {12 ????while (scanf("%d",&n)!=EOF)13 ????{14 ????????for (int i=1;i<=n;i++)15 ????????????for (int j=1;j<=n;j++)16 ????????????????scanf("%d",&G[i][j]);17 ????????LL ans =0;18 ????????bool ok=1;19 ????????for (int i=1;i<=n;i++)20 ????????{21 ????????????for (int j=1;j<=n;j++)22 ????????????{23 ????????????????if (i==j) continue;24 ????????????????bool need=1;25 ????????????????for (int k=1;k<=n;k++)26 ????????????????{27 ????????????????????if (k==i||k==j) continue;28 ????????????????????if (G[i][j]>G[i][k]+G[k][j]) ?ok=0;29 ????????????????????if (G[i][j]==G[i][k]+G[k][j]) need=0;30 ????????????????}31 ????????????????if (need) ans+=G[i][j];32 ????????????}33 ????????}34 ????????if (ok) printf("%lld\n",ans/2);35 ????????else printf("-1\n");36 ????}37 ????return 0;38 }