无向图最短路径
测试数据来自 system/2024
描述
无向图最短路径问题,是图论中最经典也是最基础的问题之一。本题我们考虑一个有 \(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
- 1019
- 难度
- 10
- 分类
- (无)
- 标签
- (无)
- 递交数
- 1
- 已通过
- 0
- 通过率
- 0%
- 上传者