Submission #1275798


Source Code Expand

#include <bits/stdc++.h>
using namespace std;

int main()
{
	int T, N;
	cin >> T;
	while (T--) {
		cin >> N;
		vector<int> a(N);
		vector<vector<int>> G(N, vector<int>(N));
		for (int i = 0; i < N; i++) {
			for (int j = 0; j < N; j++) {
				cin >> G[i][j];
				if (G[i][j] == -1) {
					G[i][j] = 1000000;
				}
			}
		}
		bool res = true;
		for (int i = 0; i < N; i++) {
			if (G[i][i]) {
				res = false;
			}
		}
		for (int k = 0; k < N; k++) {
			for (int i = 0; i < N; i++) {
				for (int j = 0; j < N; j++) {
					if (G[i][j] > G[i][k] + G[k][j]) {
						res = false;
					}
				}
			}
		}
		cout << (res ? "YES" : "NO") << endl;
	}
	return 0;
}

Submission Info

Submission Time
Task C - 最短経路
User kazuma
Language C++14 (GCC 5.4.1)
Score 100
Code Size 691 Byte
Status AC
Exec Time 8 ms
Memory 256 KB

Judge Result

Set Name All
Score / Max Score 100 / 100
Status
AC × 41
Set Name Test Cases
All 00_sample.txt, 10_random_00.txt, 10_random_01.txt, 10_random_02.txt, 10_random_03.txt, 10_random_04.txt, 10_random_05.txt, 10_random_06.txt, 10_random_07.txt, 10_random_08.txt, 10_random_09.txt, 10_random_10.txt, 10_random_11.txt, 10_random_12.txt, 10_random_13.txt, 10_random_14.txt, 10_random_15.txt, 10_random_16.txt, 10_random_17.txt, 10_random_18.txt, 10_random_19.txt, 10_random_20.txt, 10_random_21.txt, 10_random_22.txt, 10_random_23.txt, 10_random_24.txt, 10_random_25.txt, 10_random_26.txt, 10_random_27.txt, 10_random_28.txt, 10_random_29.txt, 22_random_30.txt, 22_random_31.txt, 23_coplete_32.txt, 23_coplete_33.txt, 24_path_34.txt, 24_path_35.txt, 25_tree_36.txt, 25_tree_37.txt, 26_noedge_38.txt, 27_dot_39.txt
Case Name Status Exec Time Memory
00_sample.txt AC 1 ms 256 KB
10_random_00.txt AC 7 ms 256 KB
10_random_01.txt AC 8 ms 256 KB
10_random_02.txt AC 7 ms 256 KB
10_random_03.txt AC 7 ms 256 KB
10_random_04.txt AC 8 ms 256 KB
10_random_05.txt AC 8 ms 256 KB
10_random_06.txt AC 7 ms 256 KB
10_random_07.txt AC 8 ms 256 KB
10_random_08.txt AC 7 ms 256 KB
10_random_09.txt AC 7 ms 256 KB
10_random_10.txt AC 7 ms 256 KB
10_random_11.txt AC 7 ms 256 KB
10_random_12.txt AC 7 ms 256 KB
10_random_13.txt AC 8 ms 256 KB
10_random_14.txt AC 8 ms 256 KB
10_random_15.txt AC 7 ms 256 KB
10_random_16.txt AC 7 ms 256 KB
10_random_17.txt AC 7 ms 256 KB
10_random_18.txt AC 7 ms 256 KB
10_random_19.txt AC 7 ms 256 KB
10_random_20.txt AC 8 ms 256 KB
10_random_21.txt AC 7 ms 256 KB
10_random_22.txt AC 7 ms 256 KB
10_random_23.txt AC 7 ms 256 KB
10_random_24.txt AC 8 ms 256 KB
10_random_25.txt AC 7 ms 256 KB
10_random_26.txt AC 7 ms 256 KB
10_random_27.txt AC 8 ms 256 KB
10_random_28.txt AC 7 ms 256 KB
10_random_29.txt AC 7 ms 256 KB
22_random_30.txt AC 8 ms 256 KB
22_random_31.txt AC 7 ms 256 KB
23_coplete_32.txt AC 8 ms 256 KB
23_coplete_33.txt AC 8 ms 256 KB
24_path_34.txt AC 8 ms 256 KB
24_path_35.txt AC 8 ms 256 KB
25_tree_36.txt AC 7 ms 256 KB
25_tree_37.txt AC 7 ms 256 KB
26_noedge_38.txt AC 7 ms 256 KB
27_dot_39.txt AC 1 ms 256 KB