← 返回题目列表

AtCoder · kupc2015_c

C. 最短路径

中文机器翻译题面 查看原题

問題文

给出了简单有向图中任意两个顶点之间的最短距离的条件。确定是否存在满足该条件的有向图。


入力

输入是按以下格式从标准输入给出的。

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