Submission #1319305

---

Source Code Expand

#include<bits/stdc++.h>
using namespace std;
int T,n,a[30][30],b[30][30];
int main(){
	cin>>T;
	for(int i=0;i<T;i++){
		cin>>n;bool KO=false;
		for(int j=0;j<n;j++){
			for(int k=0;k<n;k++){
				cin>>a[j][k];if(a[j][k]==-1)a[j][k]=99999999;
				if(j==k && a[j][k]!=0){KO=true;}
				b[j][k]=a[j][k];
			}
		}
		for(int j=0;j<n;j++){
			for(int k=0;k<n;k++){
				for(int l=0;l<n;l++){
					if(b[k][l]>b[k][j]+b[j][l]){
						b[k][l]=b[k][j]+b[j][l];
					}
				}
			}
		}
		for(int j=0;j<n;j++){
			for(int k=0;k<n;k++){
				if(a[j][k]!=b[j][k])KO=true;
			}
		}
		if(KO==true)cout<<"NO"<<endl;
		else cout<<"YES"<<endl;
	}
	return 0;
}

Submission Info

Judge Result