[数据结构与算法]P1119 灾后重建（Floyd模板）

灾后重建 - 洛谷

/*
 * @Description: To iterate is human, to recurse divine.
 * @Autor: Recursion
 * @Date: 2022-03-11 10:05:27
 * @LastEditTime: 2022-03-11 20:24:50
 */
#include<bits/stdc++.h>
using namespace std;
int n,m;
int T[205];
int G[500][500];
void updata(int k)
{
    for(int i=0;i<n;i++)
        for(int j=0;j<n;j++)
            if(G[i][j]>G[i][k]+G[k][j])
                G[i][j]=G[j][i]=G[i][k]+G[k][j];
    return;
}

int main()
{
    cin>>n>>m;
    for(int i=0;i<n;i++)
        cin>>T[i];
    // for(int i=0;i<n;i++)//不能用memset，会炸，只有-1和0能用
    for(int i=0;i<n;i++){
        for(int j=0;j<n;j++)
            G[i][j]=1e9;
    }
    for(int i=0;i<n;i++)
        G[i][i]=0;
    // for(int i=0;i<n;i++){
    //     for(int j=0;j<n;j++)
    //         cout<<G[i][j]<<" ";
    //     cout<<endl;
    // }
    
    int x,y,w;
    for(int i=1;i<=m;i++){
        cin>>x>>y>>w;
        G[x][y]=G[y][x]=w;
    }
    int Q,now=0,t;
    cin>>Q;
    for(int i=1;i<=Q;i++){
        cin>>x>>y>>w;
        while(T[now]<=w&&now<n){
            updata(now);
            now++;
        }
        if(T[x]>w||T[y]>w) cout<<-1<<endl;
        else{
            if(G[x][y]==1e9) cout<<-1<<endl;
            else cout<<G[x][y]<<endl;
        }
    }

}