P1119 灾后重建 题解

· · 个人记录

\color{green}\text{AC算法：} floyd

题目描述

有 N 个村庄，M条公路，编号为 0 \rightarrow N-1。每个村庄都有一个修复完成时间 ti，为 0 则不需要修复。
有 q 个询问，每次询问在第 t 天，x \rightarrow y 的最短路。保证每次询问 t 是不下降的。

题目分析：

观察一下数据范围，n \le 200 ，这明显是在暗示使用 floyd这种 O(n^{3}) 暴力来求最短路。同时如此小的数据范围可以用邻接矩阵。
可以用一个结构体 czok 存储每个村庄的修复时间。用另一个结构体 node 存储每组询问。可以将 node 数组从按照 t 的大小从小到大排序，为什么这么做之后会解释。

解题过程

读入完成后，就是刚才说的将 node 数组从小到大排序。然后处理每一组询问。
对于每一组询问，可以依次遍历 n 个点求最短路。但是这样复杂度为 O(QN^{3})，恭喜你TLE了。
想一想优化，这时候就可以利用每组询问的 t 不下降的性质了。可以定义一个变量 pos = 0 ,遍历每组询问时从pos开始遍历，如果当前点 pos已经被修复，那么从 pos 跑一遍floyd，然后 pos++ ，知道 pos 没有被修复。可以发现，因为每组询问的 t （第 t 天）是不下降的，所以在之前询问中已经修复的点在当前询问中也一定已经修复，不用重新从已经跑过floyd的点中重新再跑一遍，这样每个点最多运行一次floyd，时间复杂度降为 O(q + n^{3})，可以AC。

代码：

#include <iostream>
#include <cstring>
#include <cstdio>
#include <cstdlib>
#include <cmath>
#include <algorithm>
using namespace std;
inline int read(){
    int x = 0, f = 1;
    char ch = getchar();
    while(ch<'0'||ch>'9'){
        if(ch=='-')
            f = -1;
        ch = getchar();
    }
    while(ch>='0'&&ch<='9'){
        x = (x << 1) + (x << 3) + (ch ^ 48);
        ch = getchar();
    }
    return x * f;
}
int n,m;
int dis[205][205];//距离，邻接矩阵
bool vis[205];//判断是否已经有了答案
int q;
struct Node{
    int u, t, time;
    int bh;
    int ans;
}node[50005];
struct Czok{
    int bh;//它的编号
    int time;//修复时间
}czok[205];
bool cmp(Node a,Node b){
    return a.time < b.time;
}
bool cmpbh(Node a,Node b){
    return a.bh < b.bh;
}
inline void floyd(int mid){
    for (int i = 1; i <= n;i++){
        for (int j = 1; j <= n;j++){
            dis[i][j]=min(dis[i][j],dis[i][mid]+dis[mid][j]);
        }
    }
}
int main(){
    memset(dis, 0x3f, sizeof(dis));
    n = read();
    m = read();
    for (int i = 1; i <= n;i++){
        dis[i][i] = 0;
    }
    for (int i = 1; i <= n; i++){
        czok[i].time = read();
        czok[i].bh = i;
    }
    for (int i = 1; i <= m; i++)
    {
        int u, t, v;
        u = read();
        t = read();
        v = read();
        u++;//因为题目中起点是由0开始的，这里使用下标1，所以下标++
        t++;
        dis[u][t] = min(dis[u][t],v);//重边保留最小
        dis[t][u] = min(dis[t][u], v);
    }
    q = read();
    for (int i = 1; i <= q;i++){
        int u, t, time;
        u = read();
        t = read();
        time = read();
        u++;//原理同上
        t++;
        node[i].bh=i;
        node[i].u = u;
        node[i].t = t;
        node[i].time = time;
    }
    sort(node + 1, node + q + 1, cmp);
    int pos = 1;//遍历所有村庄，遇到修复的就跑一边floyd
    for (int i = 1; i <= q;i++)
    {
        while(czok[pos].time<=node[i].time&&pos<=n){
            //如果已经修复完成，并且没有越界，跑一边floyd
            int bh=czok[pos].bh;
            floyd(bh);
            vis[bh] = 1;
            pos++;
        }
        if(!vis[node[i].u]||!vis[node[i].t]||dis[node[i].u][node[i].t]>100000000)
            node[i].ans = -1;
        else
            node[i].ans = dis[node[i].u][node[i].t];
    }
    sort(node + 1, node + q + 1, cmpbh);
    for (int i = 1; i <= q;i++){
        cout << node[i].ans << endl;
    }
    return 0;
}