C++11(clang++ 3.9) 解法, 执行用时: 385ms, 内存消耗: 4452K, 提交时间: 2020-02-15 15:42:39

#include<cstdio>
#include<iostream>
#include<algorithm>
#include<cstring>
#include<cmath>
using namespace std;
#define ll long long
int n,num[505],top,opt;
ll inf=1e9+1;
ll chk[505][505];
ll ans[505][505];
int main()
{
	scanf("%d",&n);
	for(int i=1;i<=n;i++)
	for(int j=1;j<=n;j++)
	{
		scanf("%lld",&chk[i][j]);
		if(j<i&&chk[i][j]!=chk[j][i]){opt=1;}
		ans[i][j]=chk[i][j];
	}
	for(int k=1;k<=n;k++)
	for(int i=1;i<=n;i++)
	for(int j=1;j<=n;j++)
	ans[i][j]=min(ans[i][j],ans[i][k]+ans[k][j]);
	
	for(int i=1;i<=n;i++)
	for(int j=1;j<=n;j++)
	{
		if(ans[i][j]!=chk[i][j])opt=1;
	}
	
	
	for(int k=1;k<=n;k++)
	for(int i=1;i<=n;i++)
	for(int j=1;j<=n;j++)
	if(i!=j&&j!=k&&i!=k&&ans[i][j]==ans[i][k]+ans[k][j])ans[i][j]=inf;
	for(int i=1;i<=n;i++)
	for(int j=i+1;j<=n;j++)
	{
		if(ans[i][j]!=inf)num[++top]=ans[i][j];
	}
	if(top!=n-1)opt=1;
	if(opt){printf("No");return 0;}
	printf("Yes\n");
	sort(num+1,num+n);
	for(int i=1;i<n;i++)
	{
		printf("%lld\n",num[i]);
	}
	
	return 0;
}

C++14(g++5.4) 解法, 执行用时: 76ms, 内存消耗: 2788K, 提交时间: 2020-02-16 14:00:25

#include<bits/stdc++.h>
using namespace std;
const int maxn=505;
long long e[maxn][maxn];
bool bk[maxn][maxn];
vector <long long> v;
int main()
{
	int n;scanf("%d",&n);
	for(int i=1;i<=n;i++){
		for(int j=1;j<=n;j++)
			scanf("%lld",&e[i][j]);
	}
	for(int i=1;i<=n;i++){
		for(int j=i+1;j<=n;j++){
			bool flag=true;
			for(int k=1;k<=n;k++){
				if((e[i][j]+e[j][k]!=e[i][k]||bk[i][k])&&
					(e[j][i]+e[i][k]!=e[j][k]||bk[j][k])){
					flag=false;break;
				}
			}
			if(flag)	v.push_back(e[i][j]),bk[i][j]=true,bk[j][i]=true;
		}
	}
//	cout<<v.size()<<endl;
	if((int)v.size()==n-1){
		printf("Yes\n");
		sort(v.begin(),v.end());
		for(int i=0;i<n-1;i++){
			printf("%lld\n",v[i]);
		}
	}
	else{
		printf("No\n");
	}
}