P1119 灾后重建题解

• 思路
• 代码

思路

首先先来分析一下算法，Floyd 算法的时间复杂度是 \(O(n^3)\) 虽然很多，但在这一题里很合适。dijkstra 算法用堆优化的时间复杂度是 \(O(m \log n)\)，在这一题里会超时。Bellman–Ford 算法的时间复杂度是 \(O(mn)\)，会超时。
所以说这一题是能用 Floyd 来解决。
那么具体的细节，就是在每一次的问答里，只要有一个满足 \(\leq time\) 的点那就用这个点来更新所有点。

代码

#include<bits/stdc++.h>
using namespace std;
const int N=205;
int n,m,f[N][N],t[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[i][k]+f[k][j];
            }
        }
    }
}
int main(){
    cin>>n>>m;
    for(int i=0;i<n;i++)for(int j=0;j<n;j++)f[i][j]=1e9;
    for(int i=0;i<n;i++)f[i][i]=0;
    for(int i=0;i<n;i++)cin>>t[i];
    for(int i=1;i<=m;i++){
        int u,v,w;cin>>u>>v>>w;
        f[u][v]=f[v][u]=w;
    }
    int q;cin>>q;
    int i=0;
    while(q--){
        int x,y,time;cin>>x>>y>>time;
        if(t[x]>time||t[y]>time){
            cout<<"-1\n";
            continue;
        }
        while(t[i]<=time&&i<n){
            update(i);
            i++;
        }
        if(f[x][y]==1e9)cout<<"-1\n";
        else cout<<f[x][y]<<"\n";
    }
}