AtCoder Beginner Contest 074

D - Restoring Road Network

//
Sample Input 1 
Copy
3
0 1 3
1 0 2
3 2 0
Sample Output 1 
Copy
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 
Copy
3
0 1 3
1 0 1
3 1 0
Sample Output 2 
Copy
-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 
Copy
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 
Copy
82
Sample Input 4 
Copy
3
0 1000000000 1000000000
1000000000 0 1000000000
1000000000 1000000000 0
Sample Output 4 
Copy
3000000000

//
#include
using namespace std;

typedef long long LL;
const int N=333;
int map_in[N][N];
int flag[N][N];

int main()
{
    int n,i,j,k; LL ans=0;

    scanf("%d",&n);
    
    for( i=1;i<=n;i++ )
        for( j=1;j<=n;j++ )
            scanf("%d",&map_in[i][j]);
    
    for( i=1;i<=n;i++ )
        for( j=1;j<=n;j++ )
            for( k=1;k<=n;k++ )
            {
                if( i==j || i==k || j==k ) continue;
                if( map_in[i][j] > map_in[i][k]+map_in[k][j] ) { printf("-1n"); return 0; }    // 不存在的图
                if( map_in[i][j] == map_in[i][k]+map_in[k][j] ) flag[i][j]=flag[j][i]=1;        // 去重
            }                                                   // 检查写重了没

    for( i=1;i<=n;i++ )
        for( j=1;j<=n;j++ )             
            if( flag[i][j]==0 && i!=j ) ans+=map_in[i][j];

    printf("%lldn",ans/2);         // 去重 i->j j->i

    return 0;
}