P4779 【模板】单源最短路径（标准版）——题解

解题思路

边权非负，使用堆优化 Dijkstra。距离数组初始化为无穷，源点为 0。优先队列每次取当前距离最小且尚未确定的结点，用它尝试松弛所有出边。

复杂度分析

时间复杂度 $O((n+m)\log n)$，空间复杂度 $O(n+m)$。

易错点

边权和需要使用 long long 保存；优先队列中可能存在旧状态，需用访问标记或比较距离跳过。

C++17 参考代码

#include <bits/stdc++.h>
using namespace std;
using ll=long long;
const ll INF=(1LL<<62);
int main(){
    ios::sync_with_stdio(false); cin.tie(nullptr);
    int n,m,s; cin>>n>>m>>s;
    vector<vector<pair<int,int>>> g(n+1);
    for(int i=0;i<m;i++){int u,v,w;cin>>u>>v>>w;g[u].push_back({v,w});}
    vector<ll> d(n+1,INF); vector<char> vis(n+1,0);
    priority_queue<pair<ll,int>,vector<pair<ll,int>>,greater<pair<ll,int>>> q;
    d[s]=0; q.push({0,s});
    while(!q.empty()){
        auto [du,u]=q.top(); q.pop();
        if(vis[u]) continue; vis[u]=1;
        for(auto [v,w]:g[u]) if(d[v]>du+w){d[v]=du+w;q.push({d[v],v});}
    }
    for(int i=1;i<=n;i++) cout<<d[i]<<(i==n?'\n':' ');
    return 0;
}

#include <bits/stdc++.h> using namespace std; using ll=long long; const ll INF=(1LL<<62); int main(){ ios::sync_with_stdio(false); cin.tie(nullptr); int n,m,s; cin>>n>>m>>s; vector<vector<pair<int,int>>> g(n+1); for(int i=0;i<m;i++){int u,v,w;cin>>u>>v>>w;g[u].push_back({v,w});} vector d(n+1,INF); vector vis(n+1,0); priority_queue<pair<ll,int>,vector<pair<ll,int>>,greater<pair<ll,int>>> q; d[s]=0; q.push({0,s}); while(!q.empty()){ auto [du,u]=q.top(); q.pop(); if(vis[u]) continue; vis[u]=1; for(auto [v,w]:g[u]) if(d[v]>du+w){d[v]=du+w;q.push({d[v],v});} } for(int i=1;i<=n;i++) cout<<d[i]<<(i==n?'\n':' '); return 0; }