P5905 【模板】全源最短路（Johnson）
题目描述
给定一个包含 $n$ 个结点和 $m$ 条带权边的有向图，求所有点对间的最短路径长度，一条路径的长度定义为这条路径上所有边的权值和。
注意：
1. 边权**可能**为负，且图中**可能**存在重边和自环；
2. 部分数据卡 $n$ 轮 SPFA 算法。
输入格式
无
输出格式
无
说明/提示
【样例解释】
左图为样例 $1$ 给出的有向图，最短路构成的答案矩阵为：
```
0 4 11 8 11
1000000000 0 7 4 7
1000000000 -5 0 -3 0
1000000000 -2 5 0 3
1000000000 -1 4 1 0
```
右图为样例 $2$ 给出的有向图，红色标注的边构成了负环，注意给出的图不一定连通。
【数据范围】
对于 $100\%$ 的数据，$1\leq n\leq 3\times 10^3,\ \ 1\leq m\leq 6\times 10^3,\ \ 1\leq u,v\leq n,\ \ -3\times 10^5\leq w\leq 3\times 10^5$。
对于 $20\%$ 的数据，$1\leq n\leq 100$，不存在负环（可用于验证 Floyd 正确性）
对于另外 $20\%$ 的数据，$w\ge 0$（可用于验证 Dijkstra 正确性）
upd. 添加一组 Hack 数据：针对 SPFA 的 SLF 优化