AT_kupc2015_c 最短経路

给定一个简单有向图中任意两点间的最短距离的条件。请判断是否存在满足这些条件的有向图。

输入由多组测试用例组成，通过标准输入给出。 第一行包含一个整数 $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$）。如果 $a_{ij} = -1$，表示从顶点 $i$ 到顶点 $j$ 不存在路径；否则，$a_{ij}$ 表示从顶点 $i$ 到顶点 $j$ 的最短距离。

如果存在满足条件的有向图，输出 `YES`；否则输出 `NO`。

由 ChatGPT 4.1 翻译