seuOJ247 - 小雅米的无向连通图

• 题目类型：传统
• 输入文件：标准输入流
• 输出文件：标准输出流
• 时间限制：1000 ms
• 空间限制：256 MiB
• 题目标签：冬季, 校赛, 2019

题目描述

小雅米有一张 $n$ 个点的任意边边权非负的无向连通图，刚刚学会了 Floyd 算法的小雅米计算这张无向连通图的两两点对之间的最短路的距离。然而贪玩的小雅米弄丢了这张无向连通图。现在他急得哇哇大哭，现在希望你帮助小雅米得到一张任意两点之间最短路的距离和原来相同的图。

注意：任意一张任意两点间最短路的距离和输入相同的图都算作正确答案，并不要求最优化任何条件。

输入格式

第一个一个正整数 $n(1 \leq n \leq 100)$，代表图中点的数量。

下面 $n$ 行每行 $n$ 个非负整数，其中第 $i$ 行第 $j$ 个整非负数 $d_{i,j}$ 表示从顶点 $i$ 到顶点 $j$ 的最短路的长度。数据保证对于任意 $i,j$ 都有$d_{i,j}=d_{j,i}$ 且 $0 \leq d_{i,j} \leq 10^8$，并且对于任意 $i$ 都有 $d_{i,i}=0$

输出格式

$n$ 行 $n$ 个整数其中第 $i$ 行第 $j$ 个整数 $g_{i,j} \geq -1$。

$g_{i,j} \geq 0$ 时表示顶点 $i$ 到顶点 $j$ 间有一条边权为 $g_{i,j}$ 的边，$g_{i,j}=-1$ 代表顶点 $i$ 到顶点 $j$ 之间没有边。

要求当 $i=j$ 时 $g_{i,j}=0$ 且对于任意 $i,j$ 都有 $g_{i,j}=g_{j,i}$。

当输出不满足要求时会被直接判 Wrong Answer。

样例

输入样例

3
0 4 9
4 0 5
9 5 0

输出样例

0 4 -1
4 0 5
-1 5 0