AT_kupc2015_c.最短経路

通过率：0%

AC君温馨提醒

该题目为【atcoder】题库的题目，您提交的代码将被提交至atcoder进行远程评测，并由ACGO抓取测评结果后进行展示。由于远程测评的测评机由其他平台提供，我们无法保证该服务的稳定性，若提交后无反应，请等待一段时间后再进行重试。

题目描述

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

输入格式

输入由多组测试用例组成，通过标准输入给出。

第一行包含一个整数 $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。

输入输出样例

输入#1

输出#1

YES
NO
YES
NO

说明/提示

由 ChatGPT 4.1 翻译

输入解题思路，AI测评打分。不知道怎么写?

首页