G8024 [GESP202609 八级] 末班车 题解

知识点：反向图、优先队列、最晚出发时间。

解题思路

对每个终点反向求最晚可出发时间。若从u到v的末班为l、耗时t，已知v最晚可到val，则u最晚为min(l,val-t)。用大根堆最大化各点期限，查询比较late[y][x]与出发s。

为什么正确

赶上后续路径与赶上当前线路分别给出两个时间上界，取最小是该后继的准确可行期限；对所有后继取最大得到完整最优期限。

易错点

线路有方向，反向建图只用于倒推；同一分钟到达可立即换乘，比较包含等号，不要额外减1。

复杂度

预处理O(n(n+m)log n)，单次查询O(1)，空间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,q;
    cin>>n>>m>>q;
    struct E {
        int u,l,t;
    }
    ;
    vector<vector<E>>rev(n+1);
    while(m--) {
        int u,v,l,t;
        cin>>u>>v>>l>>t;
        rev[v].push_back({u,l,t});
    }
    vector<vector<int>>late(n+1,vector<int>(n+1,-1));
    for(int dst=1;dst<=n;dst++) {
        priority_queue<pair<int,int>>pq;
        late[dst][dst]=1000000000;
        pq.push({1000000000,dst});
        while(!pq.empty()) {
            auto [val,u]=pq.top();
            pq.pop();
            if(val!=late[dst][u])continue;
            for(auto e:rev[u]) {
                int next=min(e.l,val-e.t);
                if(next>late[dst][e.u]) {
                    late[dst][e.u]=next;
                    pq.push({next,e.u});
                }
            }
        }
    }
    while(q--) {
        int x,y,s;
        cin>>x>>y>>s;
        cout<<(late[y][x]>=s?"Yes":"No")<<"\n";
    }
}

说明

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