KUPC2015 : C - 最短経路

これは割とすぐ思いついた。
http://kupc2015.contest.atcoder.jp/tasks/kupc2015_c

問題

N頂点の有向グラフが与えられる。
各辺には距離が設定されている。

このグラフについて、２点間の最短距離を示した筈の２次元配列が与えられる。
本当にこの２次元配列は２点間の最短距離を示したものとして妥当か検証せよ。

解法

対角成分が0以外の場合はそもそも妥当ではない。
それ以外の場合、再度Warshall-Floydを実行して値が変わらなければ妥当と考えられる。

int T;
int N;
int A[50][50];
int B[50][50];

void solve() {
	int i,j,k,l,r,x,y,z; string s;
	
	cin>>T;
	while(T--) {
		int ok=1;
		cin>>N;
		FOR(y,N) FOR(x,N) {
			cin>>A[x][y];
			if(A[x][y]==-1) A[x][y]=10000000;
			B[x][y]=A[x][y];
		}
		FOR(z,N) FOR(x,N) FOR(y,N) A[x][y]=min(A[x][y],A[x][z]+A[z][y]);
		FOR(y,N) if(A[y][y]!=0) ok=0;
		FOR(y,N) FOR(x,N) if(A[x][y]!=B[x][y]) ok=0;
		
		out:
		cout<<(ok?"YES":"NO")<<endl;
	}
}

まとめ

シンプルだけどちょっと考える感じの問題でいいね。
でもどっかに類題出てそうな気もする。