洛谷 P5905 题目模板 Johnson全源最短路（基于SPFA判负环的 Johnson算法实现）

【模板】Johnson 全源最短路

题目描述

针对一个由 n 个顶点与 m 条赋权有向边构成的图，目标是计算任意两点之间的最短路径长度。此处所指的路径长度，即为该路径中所有边权重的总和。

需注意以下几点：

边的权重有可能为负值，并且图中可能存在多重边以及自环；

某些测试数据会对基于 n 次迭代的 SPFA 算法造成限制。

输入格式

第 1 行：给出 2 个整数 n,m，分别代表所给有向图中节点的总数以及有向边的数量。

随后的 m 行中，每行包含 3 个整数 u,v,w，用以描述一条从编号为 u 的节点指向编号为 v 的节点、且权重为 w 的有向边。

输出格式

当图中包含负环时，仅需输出一行 -1。

若图中未检测到负环：

需输出 n 行内容。设 dis_{i,j} 表示从节点 i 到节点 j 的最短路径长度，在第 i 行应输出 \sum\limits_{j=1}^n j\times dis_{i,j}，请注意该数值可能超出 int 类型的存储范围。

对于无法从 i 到达 j 的情况，定义 dis_{i,j}=10^9；而当 i=j 时，则规定 dis_{i,j}=0。

样