【代码超详解】洛谷 P1119 灾后重建（Floyd算法）

一、题目描述

二、算法分析说明与代码编写指导

以下是Floyd算法：

设带权连通图G(V, E)，边权代表边长（直接相连两点的通路长度），二维数组d[i][j]表示顶点i到顶点j的最小通路距离，其中通路还允许
经过0到k－1顶点（可以包含i、j，但多次经过一个点（存在环）的路径肯定不是最短的，会被筛掉）。
算法的原理是：如果一条路径仅经过若干个点，且已确认是最短路径，那么如果仍然想尝试继续缩短，只能再允许路径中增加一个允许经过的
顶点。从两个邻接点开始不断引入顶点，就可以形成递推关系求得任意两点的最短路径。
初始条件：d[i][i] = 0（除非题目有特殊要求），i = 0，1，2，……，|V|－1（设顶点编号从0到|V|－1）；d[i][j] = |ij|或大数M。
这代表顶点i到顶点j的直连边的长度，等于两个邻接点之间的最短路径。如果i与j不邻接，则距离暂时记为M。
启动递推：d[i][j] = min(d[i][j]，d[i][k] + d[k][j])，k = 1，2，3，……，|V|－1。
当最小值取d[i][j]时，代表该最短路径不经过k顶点。当最小值取d[i][k] + d[k][j]时，代表该最短路径经过k顶点。更新之前，
d[i][j]代表不经过k点的由i到j的最短路径。
对任意的一对顶点<i, j>，都要枚举由i到j的路径可能通过的全部顶点，所以需要三重循环，循环变量从外层到内层依次为k、i、j，
不能对调。算法的时间复杂度为O(|V|3)。
可以看出，Floyd-Warshall算法本质上是一个动态规划的算法。当时间要求不高时，由于该算法编写简便，可以直接采用。
应用此算法时，d数组即保存了图的全部元素。

算法性质：
当图上的两点u，v不连通时，其距离d[u][v] = M。

坑点小结：
【1】两点之间可以拥有多于1条边，此时应该保存最短的边，否则会求出错误的最短路，导致WA。
【2】即使只求一对或少数几对点之间的最短路径，也需要以O(|V|3)的复杂度跑完整个图，否则会WA。举例说明：
		for (unsigned k = 0; k < N; ++k)d[u][v] = min(d[u][v], d[u][k] + d[k][v])
如果只需要求u、v两点的最短路径，当只以循环变量k进行单层循环时，更新的只是由两条直连边组成的最短路径，而两点之间的最短路径可能
不止两条边，也可能只有1条边，所以只能老老实实将图中全部点对的最短路径全部计算出来。
【3】循环变量k必须放在最外层，原因也与【2】相同：在允许多经过下一个点来尝试继续缩短路径之前，必须让任意两个点都在经过尽可能
少的点的情况下充分缩短路径，否则会让后续求得的路径中可能有不是最短路径的一段包含在中间，导致结果出错。简单来说，Floyd算法的
本质是DP，而DP用于解决一种多阶段决策的问题。对于这类问题，每个阶段的结果仅由上一个阶段的结果决定。要使每个阶段给出的都是
最优解，那么上一个阶段必须也给出最优解。而最外层的变量k就刻画了这个“阶段”。

对本题而言，将重建完毕并通车的时间 t 当成算法描述中的 k 用即可。由于保证两个村庄只有 1 条通路，所以不用去除重边。
先初始化邻接矩阵，保存无向图的边长，用递增的数组 t 保存每个村庄重建完毕并通车的时间。
因为询问第 T0 天的情况时保证 T0 不下降，所以可以直接在每次询问时，将 t0 及以前的村庄依次开放来模拟已通车的村庄，然后计算一次最短路。T0 时仍未通车的村庄由 k 和递增数组 t 配合令其不被纳入最短路的计算过程。输出的时候，如果请求的村庄中有 1 个的通车时间比询问时间晚，则该村庄并未通车，对外无通路，输出

-1

否则输出最短路的长度即为答案。如果无通路，也要输出

-1

三、AC 代码

#include<cstdio>
#include<algorithm>
#pragma warning(disable:4996)
using namespace std;
const unsigned M = 1 << 30;
unsigned T0, t[200], d[200][200], k, m, n, q, w, x, y;
int main() {
	scanf("%u%u", &n, &m);
	for (unsigned i = 0; i < n; ++i)scanf("%u", &t[i]);
	for (unsigned i = 0; i < n; ++i)fill(d[i], d[i] + n, M), d[i][i] = 0;
	for (unsigned i = 0; i < m; ++i)scanf("%u%u%u", &x, &y, &w), d[x][y] = d[y][x] = w;
	scanf("%u", &q); ++q; k = 0;
	while (--q) {
		scanf("%u%u%u", &x, &y, &T0);
		for (; t[k] <= T0 && k < n; ++k)
			for (unsigned i = 0; i < n; ++i)
				for (unsigned j = 0; j < n; ++j)d[i][j] = min(d[i][j], d[i][k] + d[k][j]);
		if (t[x] > T0 || t[y] > T0) { puts("-1"); continue; }
		switch (d[x][y]) {
		case M:puts("-1"); continue;
		default:printf("%u\n", d[x][y]);
		}
	}
	return 0;
}