题解 P1119 【灾后重建】

HoshiuZ · 2019-10-27 23:39:24 · 个人记录

点建立需要时间，再加上看到数据范围为200，所以Floyd，况且这题用Floyd还有个好处，就是本题的点是按照时间顺序出现的，所以可以出现个点就用这个点扩展其他两点的最短路，因而想到了Floyd就是把一个点做中继点扩展其它两点的最短路的，而且查询的时间也是按照不下降顺序排的，所以每次查询就把该时间点及以前出现的点全部用于扩展。但是若查询的点出现的时间均大于查询的时间，那么也是非法的。

#include<bits/stdc++.h>

using namespace std;

int n,t,m,dis[210][210],date[210],now=0;

void initialize() {
    for(int i=0;i<n;i++) {
        for(int j=0;j<n;j++) dis[i][j]=1e9;
    }
    for(int i=0;i<n;i++) dis[i][i]=0;
}

void Floyd(int k) {
    for(int i=0;i<n;i++) {
        for(int j=0;j<n;j++) {
            if(dis[i][j]>dis[i][k]+dis[k][j]) dis[i][j]=dis[j][i]=dis[i][k]+dis[k][j];
        }
    }
}

int main() {
    cin>>n>>m;
    initialize();
    for(int i=0;i<n;i++) cin>>date[i];
    for(int i=0;i<m;i++) {
        int x,y;
        cin>>x>>y;
        cin>>dis[x][y];
        dis[y][x]=dis[x][y];
    }

    cin>>t;
    while(t) {
        int x,y,t_i;
        cin>>x>>y>>t_i;
        while(date[now]<=t_i&&now<n) {
            Floyd(now);
            now++;
        }
        if(dis[x][y]==1e9||date[x]>t_i||date[y]>t_i) cout<<-1<<endl;
        else cout<<dis[x][y]<<endl;
        t--;
    }

    return 0;
}