[Floyd] post disaster reconstruction

1️⃣ Title Description

Topic link ：
https://www.luogu.com.cn/problem/P1119

The conscience of this problem is that the reconstruction time is sorted from small to large , And the reconstruction time of inquiry is also sorted from small to large , So we can operate forward , There is no need to sort .

---

2️⃣ Simple ideas

The main problem is Floyd An understanding and practice of the essence of Algorithm .

Floyd In the algorithm k It means Intermediate nodes , Taking this as the intermediate node can update the shortest distance between two points .

$f[i][j]$: It stands for i To j The shortest distance
Whenever an inquiry is made , If a village is rebuilt before the time point asked , Take this village as the transit node , Update the shortest distance of all points .

Updated code ：

while(a[k] <= t && k < n)
{
    
	for(int i = 0; i < n; i++)
		for(int j = 0; j < n; j++)
		{
    
			if(f[i][k] + f[k][j] < f[i][j])
				f[j][i] = f[i][j] = f[i][k] + f[k][j];
		}
	k ++;
}

---

#include<bits/stdc++.h>
using namespace std;
using ll = long long;

int main()
{
    
	ios::sync_with_stdio(false);
	cin.tie(nullptr);

	int n, m;
	cin >> n >> m;
	vector<int> a(n);
	for(int i = 0; i < n; i++) cin >> a[i];
	
	vector f(n, vector(n, 1e9));
	 	
	for(int i = 0; i < n; i++)	f[i][i] = 0;
	for(int i = 1; i <= m; i++)
	{
    
		int a, b, c;
		cin >> a >> b >> c;
		f[a][b] = f[b][a] = c;
	}
	int q;
	int k = 0;
	cin >> q;
	while(q--)
	{
    
		int x, y, t;
		cin >> x >> y >> t;
		
		while(a[k] <= t && k < n)
		{
    
			for(int i = 0; i < n; i++)
				for(int j = 0; j < n; j++)
				{
    
					if(f[i][k] + f[k][j] < f[i][j])
						f[j][i] = f[i][j] = f[i][k] + f[k][j];
				}
			k ++;
		}
		
		if(a[x] > t || a[y] > t) cout << -1 << "\n";
		else 
		{
    
			if(f[x][y] == 1e9) cout << -1 << "\n";
			else cout << f[x][y] << "\n";
		} 
		
	}
	
	return 0;
}