题目详情题解（0）讨论（0）提交记录（0）

AT_arc083_b.[ABC074D] Restoring Road Network

提高+/省选-

通过率：0%

AC君温馨提醒

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

题目描述

题面翻译

曾经存在的高桥王国有N个城市，城市与城市之间用长度为正整数的无向道路连接。

现有一考古学家找到了一张N×N的表A，这张表代表了这N座城市两两之间的最短路。即表中的第u行第v列的值代表了从城市u到v的最短路长度。

问能否根据这张表，求出高桥王国的最小道路长度总和。

输入格式

第一行：N
下面是大小为N×N的表A

输出格式

一个整数，表示最小道路长度总和。如果无解，输出−1

数据范围与约定

  • 1 <= N <= 300
  • 当 i != j 时，1 <= 表A中第i行第j列的值 == 表A中第j行第i列的值 <= 10^9
  • 表A中第i行第i列的值为0

样例1解释

  • 从城市1到城市2有长度为1的直接道路
  • 从城市2到城市3有长度为2的直接道路
  • 从城市1到城市3无直接道路

样例2解释

从城市1走到城市2要走长度为1的道路，从城市2走到城市3要走长度为1的道路，所以从城市1到城市3要走的距离为2，但表中是3，所以无解。

输入输出样例

  • 输入#1

    3
0 1 3
1 0 2
3 2 0

    输出#1

    3

  • 输入#2

    3
0 1 3
1 0 1
3 1 0

    输出#2

    -1

  • 输入#3

    5
0 21 18 11 28
21 0 13 10 26
18 13 0 23 13
11 10 23 0 17
28 26 13 17 0

    输出#3

    82

  • 输入#4

    3
0 1000000000 1000000000
1000000000 0 1000000000
1000000000 1000000000 0

    输出#4

    3000000000

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

首页