luogu P1119 灾后重建 Floyd应用

#include<iostream>
#include<cstdio>
using namespace std;
const int N=205;
int n,m;
int t[N];
int f[N][N];
void update(int k)
{
	for(int i=0; i<n; i++)
		for(int j=0; j<n; j++)
			if(f[i][j]>f[i][k]+f[k][j])
				f[i][j]=f[j][i]=f[i][k]+f[k][j];
}
int main()
{
	cin>>n>>m;
	for(int i=0; i<n; i++)
		cin>>t[i];
	for(int i=0; i<n; i++)
		for(int j=0; j<n; j++)
			if(i==j)
				f[i][j]=f[j][i]=0;
			else
				f[i][j]=f[j][i]=1e9;
	for(int i=1; i<=m; i++)
	{
		int a,b,c;
		cin>>a>>b>>c;
		f[a][b]=f[b][a]=c;
	}
	int now=0;
	int Q;
	cin>>Q;
	while(Q--)
	{
		int x,y,k;
		cin>>x>>y>>k;
		while(t[now]<=k && now<n)
		{
			update(now);
			now++;
		}
		if(t[x]>k || t[y]>k || f[x][y]>=1e9 )
			cout<<"-1"<<endl;
		else
			cout<<f[x][y]<<endl;
	}
}

luogu P1119 灾后重建 Floyd应用

原文：https://www.cnblogs.com/QingyuYYYYY/p/12885232.html