D - Restoring Road Network

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

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

Sample Output 4

3000000000
题目意思:有一张地图上面标志着每个点之间最短路的大小;判断总路程;如果最短路和地图不符合就输出-1;
解题思路:Floyd算法,如果两点之间进行了中转就记录;最后遍历判断,把所有没有经过中转的路相加;
代码:

#include<iostream>#include<string>#include<algorithm>#include <string.h>#include <stdio.h>#include <math.h>#include <set>#include <queue>#include <stack>#include <map> using namespace std;typedef long long LL;const int MAX = 330; int visit[MAX][MAX]={0};LL Map1[MAX][MAX];LL Map[MAX][MAX];int N; int main(){ ???cin>>N; ???for(int i = 1;i<=N;i++) ???for(int j = 1;j<=N;j++) ???{ ???????cin>>Map[i][j]; ???????Map1[i][j] = Map[i][j]; ???} ???for(int k = 1;k<=N;k++) ???????for(int i = 1;i<=N;i++) ???????????for(int j = 1;j<=N;j++){ ???????????????if(Map[i][j]>=Map[i][k]+Map[k][j]&&(i!=k&&j!=k)){ ???????????????????//cout<<i<<" "<<j<<" "<<k<<endl; ???????????????????Map1[i][j] = Map[i][k]+Map[k][j]; ???????????????????visit[i][j] = 1; ???????????????} ???????????} ????LL sum = 0; ???for(int i = 1;i<N;i++){ ???????for(int j = i+1;j<=N;j++) ???????{ ???????????if(Map[i][j]!=Map1[i][j]){ ????????????????cout<<"-1"<<endl; ????????????????return 0; ???????????} ???????????if(Map[i][j]==Map1[i][j]&&visit[i][j]!=1) ???????????????sum+=Map[i][j]; ????????} ???} ???if(sum==0) ???????cout<<-1<<endl; ???else ???????cout<<sum<<endl; ?????return 0;}