TouchStone
  请登录后使用
登录 注册
距离CSP第一轮: ??天 距离CSP第二轮: ??天 距离NOIP还有: ??天
 系统首页  练习题库  考试列表  判题结果  信息发布  解题排行
  • 首页
  • 题库
  • P7116
  • 题目
  • P7116恢复公路网
    限制 : 时间限制 : 1000 MS   空间限制 : 262144 KB
    问题描述

    在传说中的天国里,有$N$座城市,在一些城市之间,通过双向道路相连,这些道路都有各自的长度,且是整数。天国里不同城市的人们交往只能通过这些双向道路,如果两座城市没有直达道路,但可以在某座城市中转一下也是可以交往的。

    一张可能代表了城市之间的最短距离的表格落入到你的手中,表格有$N$行$M$列,其中第$u$行、第$v$列的整数$A_{u,v}$指的是$u$城市到$v$城市的最短路径长度。你先假设表中的数据都是正确的,根据表格中的信息来推断一下天国的公路网,如果能推出公路网,说明表格中的数据是没错的,并输出这张公路网的最小总长度(所有道路之和)。如果无论如何也无法推出公路网,那说明表格中的数据可能不准确,公路网不存在,输出-1。

    其中,$1 \leq N \leq 300$

    \(i \neq j, 1 \leq A_{i,j} = A_{j,i} \leq 10^9\)

    \(A_{i,i} = 0\)

    输入格式

    按照下面标准格式输入:

    \(N\)

    \(\begin{matrix} A_{1,1} & b_{1,2} & \cdots & A_{1,N} \\ A_{2,1} & A_{2,2} & \cdots & A_{2,N}\\ \vdots \\ A_{N,1} & A_{N,2} & \cdots & A_{N,N}\end{matrix}\)

    输出格式

    如果能推出公路网,说明表格中的数据是没错的,并输出这张公路网的最小总长度(所有道路之和)。如果无论如何也无法推出公路网,那说明表格中的数据可能不准确,公路网不存在,输出-1。

    样例输入 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