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

题目大意

给定一个有向带权图（$N$ 点 $M$ 边），求从源点 $s$ 到所有其他点的最短路径长度。数据范围较大（$N le 10^5, M le 2 times 10^5$），需要 $O(M \log N)$ 级别的算法（如堆优化 Dijkstra）。

AC代码

注意，priority_queue的比较操作符与sort，set是反的

参考题解：

其实总结来讲就是使用堆然后找到dis值最小的点，将其确认为确定点（已经固定了，dis值不太可能再更新了）

https://www.luogu.com.cn/record/181960419

#include <iostream>
#include <vector>
#include <deque>
#include <cmath>
#include <queue>
#define rep(i,n) for(int i=1;i<=(n);i++)
using namespace std;
typedef long long ll;
const ll N=1e5+10,INF=1e18+7;
vector<pair<ll,ll> > g[N];
ll n,m,u,v,w,dis[N],s,vis[N];
struct cmp {
    bool operator () (pair<ll,ll> a,pair<ll,ll> b){
        if(a.second!=b.second)
            return a.second>b.second;
    }
};
priority_queue<pair<ll,ll>,vector<pair<ll,ll> >,cmp> heap;
inline void dijkstra() {
    dis[s]=0;
    heap.push(make_pair(s,0));
    while(!heap.empty()) {
        ll cn=heap.top().first,cdis=heap.top().second;  // priority_queue 需要使用.top()访问队首
        heap.pop();
        if(vis[cn])
            continue;
        vis[cn]=true;dis[cn]=cdis;                      // vis 是用来判断是不是已经确定dis的点
        for(int i=0;i<g[cn].size();i++) {
            ll ni=g[cn][i].first; ll wi=g[cn][i].second;
            heap.push(make_pair(ni,cdis+wi));
        }
    }
}
int main()
{
    ios::sync_with_stdio(false);
    cin.tie(0);
    cin>>n>>m>>s;
    rep(i,n) {
        dis[i]=INF;
    }
    rep(_,m) {
        cin>>u>>v>>w;
        g[u].push_back(make_pair(v,w));
    }
    dijkstra();
    ll forOut=pow(2,31)-1;
    rep(i,n) {
        if(dis[i]!=INF)
            cout<<dis[i]<<" ";
        else
            cout<<forOut<<" ";
    }
    cout<<endl;
    return 0;
}
//AC https://www.luogu.com.cn/record/181960419

心路历程（WA，TLE，MLE……）

未经堆优化的算法（其实不是Dijkstra）TLE

https://www.luogu.com.cn/record/181877100

#include <iostream>
#include <vector>
#include <deque>
#include <cmath>
#define rep(i,n) for(int i=1;i<=(n);i++)
using namespace std;
typedef long long ll;
const ll N=1e5+10,INF=1e18+7;
vector<pair<ll,ll> > g[N];
ll n,m,u,v,w,dis[N],s;
deque<pair<ll,ll> > q;
void dijkstra() {
    dis[s]=0;
    q.push_back(make_pair(s,0)); // curr_node curr_dis
    while(!q.empty()) {
        ll cn=q.front().first,cdis=q.front().second;
        for(int i=0;i<g[cn].size();i++) {
            ll ni=g[cn][i].first; ll wi=g[cn][i].second;
            if(cdis+wi<dis[ni]) {
                dis[ni]=cdis+wi;
                q.push_back(make_pair(ni,cdis+wi));
            }
        }
        q.pop_front();
    }
}
int main()
{
    ios::sync_with_stdio(false);
    cin.tie(0);
    cin>>n>>m>>s;
    rep(i,n) {
        dis[i]=INF;
    }
    rep(_,m) {
        cin>>u>>v>>w;
        g[u].push_back(make_pair(v,w));
    }
    dijkstra();
    ll forOut=pow(2,31)-1;
    rep(i,n) {
        if(dis[i]!=INF)
            cout<<dis[i]<<" ";
        else
            cout<<forOut<<" ";
    }
    cout<<endl;
    return 0;
}
// AC https://www.luogu.com.cn/record/181877100