/ Vijos / 题库 /

无向图最短路径

无向图最短路径

描述

无向图最短路径问题,是图论中最经典也是最基础的问题之一。本题我们考虑一个有 \(n\) 个结点的无向图 \(G\)。

\(G\) 是简单完全图,也就是说 \(G\) 中没有自环,也没有重边,但任意两个不同的结点之间都有一条带权的双向边。
每一条边的边权是非负实数,但我们并不知道每一条边的具体边权。

好消息是我们知道 \(G\) 中任意两点最短路径的长度\(d(i,j)\)。且保证至少有一种边权的分配方案满足得到的带权图中\(i\)与\(j\)的最短路长度恰好是\(d(i,j)\)。

下面是留给你的任务:对于任意一对点\((i,j)\),希望你能找出来所有合法的边权分配方案中\(i\)和\(j\)之间边权的最大值。

格式

输入格式

本题中,每一组数据都有多次询问,每一次询问分别给出了一个无向图\(G\)。

输入的第一行是一个整数 \(t\),表示总共的询问个数。之后依次给出每一次询问。
对于每一次询问来说,第一行给出了 \(G\) 中结点总数 \(n\)。之后\(n\)行每行有\(n\)个整数,给出了一个\(n\times n\)的矩阵 \(d\),其中第\(i\)行第\(j\)列的整数对应 \(d(i,j)\)表示\(i\)到\(j\)的最短路径长度。
因为图\(G\)是简单无向图,对角线元素\(d(i,i)\)总是\(0\),且矩形是对称的(也就是说\(d(i,j)=d(j,i)\))。

输出格式

对于每一次询问,若给定的图\(G\)有\(n\)个结点,则输出\(n\)行,每行有\(n\)个整数,描述了一个矩阵 \(a\)。矩阵的第\(i\)行第\(j\)列表示连接\(i\)和\(j\)的边的最大可能边权。如果\((i,j)\)的边权可以任意大,则输出字符串infty表示无限。
矩阵的对角线没有实质性意义,请全输出\(0\)。因为\(G\)是无向图,所以输出的矩阵\(a\)应该也是对称的(即\(a(i,j)=a(j,i)\))。
不难发现,因为给定的矩阵 \(d\) 中每一个数字都是整数,所以最大可能边权总会是整数。

样例1

样例输入1

2
3
0 2 8
2 0 10
8 10 0
3
0 1 1
1 0 1
1 1 0

样例输出1

0 2 8
2 0 infty
8 infty 0
0 1 1
1 0 1
1 1 0

限制

对于 \(20\%\) 的数据,有 \(n = 3\)。

对于 \(50\%\) 的数据,有 \(1\le n\le 10\)。

对于 \(100\%\) 的数据,有 \(1\le n\le 100\),且所有询问中\(n\)的和不超过 \(800\),对于所有的\(d\)满足\(1\le d\le 256\)。

每一组数据的时限为 \(0.5\) 秒。

信息

ID
2024
难度
4
分类
(无)
标签
(无)
递交数
337
已通过
132
通过率
39%
上传者

相关

在下列训练计划中:

RP++分类题库

在下列比赛中:

金秋重聚模拟赛