P1119 灾后重建 题解

· · 题解

前言

本题解使用 Djikstra + 堆优化，时间复杂度接近于 O(q \cdot m\log{m})，相比较于 Floyd-Warshall 算法的 O(q \cdot n^2+n^3)，本方法的时间复杂度可能更高，但对于本题可以卡线通过，请谨慎使用。

题意

题目传送门 >>

有 n 个村庄（注意编号从 0 到 n - 1）,m 条双向公路，并给出第 i 个村庄在受灾后重建完成的时间 t_i ，若 t_i 为 0 则说明一开始就可以通车。之后有 Q 个询问 xyt，求在第 t 天，从村庄 x 到村庄 y 的最短路径长度。若 x 或 y 未重建好或者无法通过重建好的村庄到达，则输出 -1。

解法

首先看到题目的第一眼就想到可以用 Dijkstra 来根据每一次询问跑一遍最短路，但这样的时间复杂度是 O(q \cdot m\log{m}) ，对于 q \le 50000 的数据范围有可能会 TLE。再看了一眼 n \le 200 就发现好像可以卡线 AC，于是就写了一发用堆优化的 Dijkstra。

AC 记录

只是一个普通的堆优化 Dijkstra，只需要在遍历与堆顶元素相连的点时判断该点是否在当前查询的时间之前（或现在）重建好，如果，没有就跳过。

注意

不使用堆优化的 Dijkstra 算法的时间复杂度为 O(n^2+m)，而使用堆优化后的时间复杂度为 O(m\log{m})，可以观察到当 m 和 n 同级时，采用堆优化会使得程序运行效率更高；但如果 m 与 n^2 同级，例如完全图等稠密图，那么使用堆优化之后的复杂度变为 O(n^2\log{n^2})，反而劣于不加优化的 Dijkstra。在实际应用时，应当根据实际数据范围来选择合适的方法。

代码

#include<bits/stdc++.h>
using namespace std;
int n, m;
const int maxn = 2e2 + 10;
int t[maxn];
struct line
{
    int v, w;
    bool operator < (const line& a) const {
        return w > a.w;
    }
};
vector<line> a[maxn];
int q;
bool vis[maxn];
int dis[maxn];
priority_queue<line> p;
void dijstra(int x, int y, int tm)
{
    memset(dis, 0x3f, sizeof(dis));
    memset(vis, false, sizeof(vis));
    p.push({x, 0});
    dis[x] = 0;
    while(!p.empty())
    {
        line now = p.top();
        p.pop();
        int u = now.v;
        if(vis[u])
            continue;
        vis[u] = true;
        for(auto it : a[u])
        {
            int v = it.v;
            int w = it.w;
            if(t[v] > tm)
                continue;
            if(dis[v] > dis[u] + w)
            {
                dis[v] = dis[u] + w;
                p.push({v, dis[v]});
            }
        }
    }
}
int main()
{
    ios::sync_with_stdio(false);
    cin.tie(0);
    cout.tie(0);
    cin >> n >> m;
    for(int i = 0; i <= n - 1; i++)
        cin >> t[i];
    for(int i = 1; i <= m; i++)
    {
        int u, v, w;
        cin >> u >> v >> w;
        a[u].push_back({v, w});
        a[v].push_back({u, w});
    }
    cin >> q;
    while(q--)
    {
        int x, y, tm;
        cin >> x >> y >> tm;
        if(t[x] > tm || t[y] > tm)
        {
            cout << -1 << "\n";
            continue;
        }
        dijstra(x, y, tm);
        if(dis[y] == 0x3f3f3f3f)
            cout << -1 << "\n";
        else
            cout << dis[y] << "\n";
    }
    return 0;
}

在输入查询的时候，可以通过判断当前的两个村庄 x 和 y 是否在查询时间之前或当时重建好，如果没有就直接输出 -1，这样就不用再单独跑一遍 Dijkstra，相当于搜索当中的剪枝来提升代码的运行效率。

注意在最后输出的时候如果当前的 dis_y=0x3f 时就表示目标点 y 无法通过已经重建好的村庄到达，此时根据题目要求需要输出 -1。

书写不易，不喜勿喷~