灾后重建

P1119 灾后重建 - 洛谷 | 计算机科学教育新生态 (luogu.com.cn)

floyd

本题考查 floyd 算法的本质：

for (int k = 1; k <= n; k++)
	for (int i = 1; i <= n; i++)
		for (int j = 1; j <= n; j++)
			f[i][j] = min(f[i][j], f[i][k] + f[k][j])

第一层循环 k 表示 i 号点 只能经过 1 - k 号点中转 到达 j 号点的最短距离

因此本题求解各个询问的过程相当于把 floyd 拆解出来，每当一个点被重建，意思为可以经过这个点中转更新最短距离，由于询问和点的重建时间都是非递减顺序，因此第 1 个点重建，就是 k = 1 跑一次后两层循环；第 2 个点重建，就是 k = 2 跑一次后两层循环 。。。

因此所有点重建的更新过程相当于只跑了一遍完整的 floyd，复杂度为 \(O(n^3+q)\)

#include 
#include 
#include 
#include 
#include 

using namespace std;
typedef long long ll;

const int N = 2e2 + 10;
const int INF = 0x3f3f3f3f;
int n, m;
int g[N][N];
int a[N];
void updata(int now)
{
	for (int i = 0; i < n; i++)
		for (int j = 0; j < n; j++)
			g[i][j] = min(g[i][j], g[i][now] + g[now][j]);
}
int main()
{
	ios::sync_with_stdio(false), cin.tie(0), cout.tie(0);
	cin >> n >> m;
	for (int i = 0; i < n; i++)
		cin >> a[i];
	memset(g, 0x3f, sizeof g);
	for (int i = 0; i < n; i++)
		g[i][i] = 0;
	while(m--)
	{
		int i, j, w;
		cin >> i >> j >> w;
		g[i][j] = g[j][i] = w;
	}
	int q;
	cin >> q;
	int now = 0;
	while(q--)
	{
		int x, y, t;
		cin >> x >> y >> t;
		while(a[now] <= t && now < n)
		{
			updata(now);
			now++;
		}
		if (a[x] > t || a[y] > t)
			cout << -1 << endl;
		else
		{
			if (g[x][y] == INF)
				cout << -1 << endl;
			else
				cout << g[x][y] << endl;
		}
	}
	return 0;
}