Submission #534083
Source Code Expand
using System; using System.Collections.Generic; using System.Linq; using System.IO; using System.Text; using System.Numerics; using System.Globalization; namespace Solver { class Program { const int M = 1000000007; const double eps = 1e-9; static void Main() { var sw = new System.IO.StreamWriter(Console.OpenStandardOutput()) { AutoFlush = false }; var sc = new Scan(); int t = sc.Int; for (int i = 0; i < t; i++) { int n = sc.Int; var a = new int[n][]; for (int j = 0; j < n; j++) a[j] = sc.IntArr; for (int j = 0; j < n; j++) { if (a[j][j] != 0) { sw.WriteLine("NO"); goto A; } } var b = WarshallFloyd(a); for (int j = 0; j < n; j++) { for (int k = 0; k < n; k++) { if (a[j][k] != b[j][k] && a[j][k] != -1) { sw.WriteLine("NO"); goto A; } } } sw.WriteLine("YES"); A: continue; } sw.Flush(); } static int[][] WarshallFloyd(int[][] g) { var d = Copy(g); int n = d.Length; for (int i = 0; i < n; ++i) for (int j = 0; j < n; ++j) for (int k = 0; k < n; ++k) d[j][k] = Math.Min(d[j][k], d[j][i] + d[i][k]); return d; } static int[][] Copy(int[][] g) { var ret = new int[g.Length][]; for (int i = 0; i < g.Length; ++i) { ret[i] = new int[g[i].Length]; for (int j = 0; j < g[i].Length; ++j) { if (g[i][j] == -1) ret[i][j] = 1000000007; else ret[i][j] = g[i][j]; } } return ret; } } class Scan { public int Int { get { return int.Parse(Console.ReadLine().Trim()); } } public long Long { get { return long.Parse(Console.ReadLine().Trim()); } } public string Str { get { return Console.ReadLine().Trim(); } } public int[] IntArr { get { return Console.ReadLine().Trim().Split().Select(int.Parse).ToArray(); } } public int[] IntArrWithSep(char sep) { return Console.ReadLine().Trim().Split(sep).Select(int.Parse).ToArray(); } public long[] LongArr { get { return Console.ReadLine().Trim().Split().Select(long.Parse).ToArray(); } } public double[] DoubleArr { get { return Console.ReadLine().Split().Select(double.Parse).ToArray(); } } public string[] StrArr { get { return Console.ReadLine().Trim().Split(); } } public List<int> IntList { get { return Console.ReadLine().Trim().Split().Select(int.Parse).ToList(); } } public List<long> LongList { get { return Console.ReadLine().Trim().Split().Select(long.Parse).ToList(); } } public void Multi(out int a, out int b) { var arr = IntArr; a = arr[0]; b = arr[1]; } public void Multi(out int a, out int b, out int c) { var arr = IntArr; a = arr[0]; b = arr[1]; c = arr[2]; } public void Multi(out int a, out int b, out int c, out int d) { var arr = IntArr; a = arr[0]; b = arr[1]; c = arr[2]; d = arr[3]; } public void Multi(out int a, out string b) { var arr = StrArr; a = int.Parse(arr[0]); b = arr[1]; } public void Multi(out int a, out int b, out string c) { var arr = StrArr; a = int.Parse(arr[0]); b = int.Parse(arr[1]); c = arr[2]; } public void Multi(out int a, out char b) { var arr = StrArr; a = int.Parse(arr[0]); b = arr[1][0]; } public void Multi(out char a, out int b) { var arr = StrArr; a = arr[0][0]; b = int.Parse(arr[1]); } public void Multi(out long a, out long b) { var arr = LongArr; a = arr[0]; b = arr[1]; } public void Multi(out long a, out int b) { var arr = LongArr; a = arr[0]; b = (int)arr[1]; } public void Multi(out string a, out string b) { var arr = StrArr; a = arr[0]; b = arr[1]; } } class mymath { int M; const double eps = 1e-9; public mymath(int M) { this.M = M; } public long pow(long a, long b) { if (b == 0) return 1; if (b == 1) return a % M; long t = pow(a, b / 2); if ((b & 1) == 0) return t * t % M; else return t * t % M * a % M; } public long gcd(long a, long b) { while (b != 0) { var t = a % b; a = b; b = t; } return a; } public long lcm(int a, int b) { return (a * b) / gcd(a, b); } } }
Submission Info
Submission Time | |
---|---|
Task | C - 最短経路 |
User | riantkb |
Language | C# (Mono 3.2.1.0) |
Score | 0 |
Code Size | 5258 Byte |
Status | WA |
Exec Time | 167 ms |
Memory | 12452 KB |
Judge Result
Set Name | All | ||||
---|---|---|---|---|---|
Score / Max Score | 0 / 100 | ||||
Status |
|
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 | 141 ms | 9740 KB |
10_random_00.txt | WA | 157 ms | 12204 KB |
10_random_01.txt | WA | 159 ms | 12196 KB |
10_random_02.txt | WA | 159 ms | 12192 KB |
10_random_03.txt | WA | 164 ms | 12200 KB |
10_random_04.txt | WA | 166 ms | 12188 KB |
10_random_05.txt | WA | 165 ms | 12196 KB |
10_random_06.txt | WA | 163 ms | 12204 KB |
10_random_07.txt | WA | 162 ms | 12128 KB |
10_random_08.txt | WA | 162 ms | 12180 KB |
10_random_09.txt | WA | 162 ms | 12212 KB |
10_random_10.txt | WA | 163 ms | 12192 KB |
10_random_11.txt | WA | 163 ms | 12196 KB |
10_random_12.txt | WA | 165 ms | 12196 KB |
10_random_13.txt | WA | 167 ms | 12188 KB |
10_random_14.txt | WA | 162 ms | 12208 KB |
10_random_15.txt | WA | 162 ms | 12204 KB |
10_random_16.txt | WA | 163 ms | 12148 KB |
10_random_17.txt | WA | 161 ms | 12204 KB |
10_random_18.txt | WA | 163 ms | 12208 KB |
10_random_19.txt | WA | 163 ms | 12192 KB |
10_random_20.txt | WA | 163 ms | 12200 KB |
10_random_21.txt | WA | 166 ms | 12192 KB |
10_random_22.txt | WA | 158 ms | 12188 KB |
10_random_23.txt | WA | 158 ms | 12112 KB |
10_random_24.txt | WA | 158 ms | 12212 KB |
10_random_25.txt | WA | 159 ms | 12164 KB |
10_random_26.txt | WA | 157 ms | 12188 KB |
10_random_27.txt | WA | 160 ms | 12188 KB |
10_random_28.txt | WA | 162 ms | 12124 KB |
10_random_29.txt | WA | 163 ms | 12156 KB |
22_random_30.txt | AC | 155 ms | 12056 KB |
22_random_31.txt | AC | 155 ms | 12056 KB |
23_coplete_32.txt | AC | 165 ms | 12452 KB |
23_coplete_33.txt | AC | 166 ms | 12320 KB |
24_path_34.txt | WA | 163 ms | 12196 KB |
24_path_35.txt | WA | 164 ms | 12104 KB |
25_tree_36.txt | WA | 162 ms | 12060 KB |
25_tree_37.txt | WA | 163 ms | 12060 KB |
26_noedge_38.txt | AC | 156 ms | 11936 KB |
27_dot_39.txt | AC | 142 ms | 9748 KB |