下文中，$dis(i,j)$ 表示 $i$ 到 $j$ 的最短路长度。$dis_{i,j}$ 表示题目给出的最短路长度。

显然，对于不同的三个点 $i,j,k$，一定满足 $dis(i,j)+dis(j,k)\ge dis(i,k)$，当且仅当 $j$ 位于 $i$ 到 $k$ 的最短路上时取等号。

考虑到极小的数据范围，我们直接暴力枚举所有的 $i,j,k$，如果 $dis_{i,j}+dis_{j,k}<dis_{i,k}$ 则返回 $-1$，如果 $dis_{i,j}+dis_{j,k}=dis_{i,k}$ 则表示 $i$ 到 $k$ 的最短路可以通过经过 $j$ 来完成，不需要额外建边。但如果不存在刚刚那样的情况，则说明必需在 $i$ 和 $k$ 之间建一条边。累加一下答案就行。

代码：

#include<bits/stdc++.h>
using namespace std;
int dis[305][305];
int main(){
	int n;
	cin>>n;
	for(int i=1;i<=n;i++){
		for(int j=1;j<=n;j++){
			cin>>dis[i][j];
		}
	}
	long long ans=0;
	for(int st=1;st<=n;st++){
		for(int ed=1;ed<=n;ed++){
			bool flag=1;
			for(int j=1;j<=n;j++){
				if(j==st || j==ed)continue;
				if(dis[st][j]+dis[j][ed]<dis[st][ed]){
					cout<<-1;
					return 0;
				}
				if(dis[st][j]+dis[j][ed]==dis[st][ed]){
					flag=0;
				}
			}
			if(flag){
				ans+=dis[st][ed];
			}
		}
	}
	cout<<ans/2;
	return 0;
}