G8011 [GESP202503 八级] 上学 题解

知识点：Dijkstra、单源最短路、优先队列。

解题思路

从学校s只运行一次Dijkstra，得到到每个点的最短路，所有查询直接输出对应距离。

为什么正确

无向图中从家到学校与学校到家的距离相同，非负边权保证Dijkstra正确，一次预处理可复用全部查询。

易错点

不能每个查询重跑最短路；松弛和距离用long long，弹堆后跳过过期状态。

复杂度

时间O((n+m)log n+q)，空间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,s,q;
    cin>>n>>m>>s>>q;
    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 d=dij(s);
    while(q--) {
        int u;
        cin>>u;
        cout<<d[u]<<"\n";
    }
}

说明

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