Submission #533441

---

Source Code Expand

#include <iostream>
#include <string>
#include <vector>
#include <algorithm>
#include <tuple>

using namespace std;
typedef tuple<int, int, int> tiii;
static const int INF = 1000000000;

int main(){
	ios_base::sync_with_stdio(false);
	int T;
	cin >> T;
	while(T--){
		int n;
		cin >> n;
		vector<vector<int>> a(n, vector<int>(n));
		for(int i = 0; i < n; ++i){
			for(int j = 0; j < n; ++j){
				cin >> a[i][j];
				if(a[i][j] < 0){ a[i][j] = INF; }
			}
		}
		vector<vector<int>> b(a);
		for(int i = 0; i < n; ++i){ b[i][i] = 0; }
		for(int k = 0; k < n; ++k){
			for(int i = 0; i < n; ++i){
				for(int j = 0; j < n; ++j){
					b[i][j] = min({ b[i][j], b[i][k] + b[k][j], INF });
				}
			}
		}
		cout << (a == b ? "YES" : "NO") << endl;
	}
	return 0;
}

Submission Info

Judge Result