京都大学プログラミングコンテスト2015

C - 最短経路


Time limit時間制限 : 2sec / Memory limitメモリ制限 : 256MB

問題文

ある単純有向グラフにおける任意の二頂点間の最短距離に関する条件が与えられる. その条件を満たす有向グラフが存在するかどうか判定せよ.


入力

入力は以下の形式で標準入力から与えられる.

T
N_1
a_{11} ... a_{1N_1}
a_{21} ... a_{2N_1}
:
a_{N_1 1} ... a_{N_1 N_1}
:
:
N_T
a_{11} ... a_{1N_T}
a_{21} ... a_{2N_T}
:
a_{N_T 1} ... a_{N_T N_T}

入力は複数のテストケースからなる.1 行目には,テストケースの個数を表す整数 T ( 1 \leq T \leq 30) が与えられる.
続いて T 個のテストケースが順に与えられる.
t ( 1 \leq t \leq T ) 番目のテストケースでは,はじめの行にグラフの頂点数を表す整数 N_t ( 1 \leq N_t \leq 30)が与えられる.
続く N_t 行にはそれぞれ N_t 個の整数が空白区切りで与えられ, i 行目の j 番目の整数 a_{ij} (1 \leq i,j \leq N_t, -1 \leq a_{ij} \leq 10000 )が -1の場合,頂点 i から頂点 j への経路が存在しないことを表し,そうでない場合は頂点 i から頂点 j への最短距離が a_{ij} であることを表す.

出力

制約を満たす有向グラフが存在する場合にはYES, しない場合にはNOを出力せよ.


入力例

4
3
0 2 3
4 0 1
3 2 0
3
0 2 4
4 0 1
3 2 0
2
0 -1
-1 0
2
0 -1
-1 1

出力例

YES
NO
YES
NO

Source name

京都大学プログラミングコンテスト2015

Submit提出する