G8017 [GESP202512 八级] 猫和老鼠 题解

知识点：Dijkstra、反向最短路、时间限制。

解题思路

先从猫窝Dijkstra求猫到达时间cat。反向从鼠洞计算每点最晚安全出发时间late，经过边(x,u)时转移min(cat[x]-1,late[u]-w)，用大根堆优先处理最大late；late≥0的点安全。

为什么正确

一条安全路径要求每个到达时刻严格早于猫，从终点倒推把后缀的安全期限与当前点期限取最小；最大化所有可选后缀得到最晚可行时间。

易错点

严格早于在整数时间上等价减1；鼠洞也要满足安全；奶酪价值总和用long long。

复杂度

时间O((n+m)log n)，空间O(n+m)。

参考代码（C++17）

#include<bits/stdc++.h>

using namespace std;
int main() {
    ios::sync_with_stdio(false);
    cin.tie(nullptr);
    int n,m,a,b;
    cin>>n>>m>>a>>b;
    vector<long long>c(n+1);
    for(int i=1;i<=n;i++)cin>>c[i];
    vector<vector<pair<int,long long>>>g(n+1);
    while(m--) {
        int u,v;
        long long w;
        cin>>u>>v>>w;
        g[u].push_back({v,w});
        g[v].push_back({u,w});
    }
    auto dij=[&](int s) {
        vector<long long>d(n+1,1LL<<60);
        priority_queue<pair<long long,int>,vector<pair<long long,int>>,greater<pair<long long,int>>>q;
        d[s]=0;
        q.push({0,s});
        while(!q.empty()) {
            auto [dist,u]=q.top();
            q.pop();
            if(dist!=d[u])continue;
            for(auto [v,w]:g[u])if(d[v]>dist+w) {
                d[v]=dist+w;
                q.push({d[v],v});
            }
        }
        return d;
    }
    ;
    auto cat=dij(a);
    vector<long long>late(n+1,-1);
    priority_queue<pair<long long,int>>pq;
    late[b]=cat[b]-1;
    pq.push({late[b],b});
    while(!pq.empty()) {
        auto [v,u]=pq.top();
        pq.pop();
        if(v!=late[u])continue;
        for(auto [x,w]:g[u]) {
            long long next=min(cat[x]-1,v-w);
            if(next>late[x]) {
                late[x]=next;
                pq.push({next,x});
            }
        }
    }
    long long ans=0;
    for(int i=1;i<=n;i++)if(late[i]>=0)ans+=c[i];
    cout<<ans;
}

说明

本题解为配套教学整理，非官方题解。复杂度按本页参考实现计算，题库使用18个自行生成的测试点。