1397_Floyd-Warshall算法

Floyd-Warshall算法是求一个图中任意两点之间的最短路径长度的算法。

给出一个有向图，请计算图中任意两个顶点之间的最短路径，及其长度。

单测试用例。

第一行是该有向图的 顶点数n  ( 0 < n < 500 )（注：图有n个顶点，首个顶点的编号是0。 ）

第二行是该有向图的 边数e   ( 0 < e < n×n )

接下来e行，每行三个整数 i 、j 和 k，表示 顶点i 到顶点j 有一条弧，长度为k。 ( 0 ≤ i, j < n )

（注：输入数据中不含 自环 。）

接下来一个正整数Q，表示有Q个询问。

接下来Q行，每行两个非负整数u和v，表示询问 顶点u 到 顶点v 的最短路长度，以及该最短路径是怎么走的。

对每个询问输出三行。

第一行是一个整数，表示顶点u到顶点v的最短路长度。如果不可达，输出INF ，且不用输出第二行。如果路径长度为0，也不用输出第二行。

第二行是若干个整数，每个整数后面跟一个空格，表示顶点u 到顶点v 的最短路的顶点序列。

第三行是一个空行，仅起分隔作用。

3
5
0 1 4
0 2 11
1 0 6
1 2 2
2 0 3
3
0 2
0 1
1 0

6
0 1 2

4
0 1

5
1 2 0

样例如下图所示

注意：本题是special judge，但validator没有写得很完美。你的代码输出时如果没有间隔的空行，PE会判为WA