本题解同时包含Dijkstra和SPFA、Dijkstra堆优化三种做法

Dijkstra朴素版时间复杂度\(O(n^2)\)，适合稠密图。使用优先队列/堆优化后为\(O(mlogn)\)

SPFA时间复杂度平均\(O(m)\)，最坏\(O(nm)\)，图中含负权边，且没有经过的边数\(l \leqslant k\)的都考虑使用SPFA。本质上是对Bellman-Ford的优化。

#include<bits/stdc++.h>
#define INF 2147483647
#define MAXN 500005
using namespace std;

int n, m, s, cnt;
int dis[MAXN], h[MAXN], to[MAXN], val[MAXN], nxt[MAXN];
bool vis[MAXN];

void add(int u, int v, int w){ // 链式前向星存图
    to[++cnt] = v;
    val[cnt] = w;
    nxt[cnt] = h[u];
    h[u] = cnt;
}

void Dijkstra(int s){
    for(int i=0; i<=n; i++) dis[i] = INF; // 初始化为无穷大
    dis[s] = 0;
    while(true){
        int u=0;
        for(int i=1; i<=n; i++){
            if(!vis[i] && dis[i]<dis[u]) u=i; // 寻找未被标记的最小的点
        }
        if ( u == 0 ) break; // 没有可处理的点，退出
        vis[u] = true; // 标记该点
        for(int i=h[u]; i; i=nxt[i]){
            int v=to[i];
            dis[v] = min(dis[v], dis[u]+val[i]); // 更新最短路
        }
    }
}

queue<int> q;
void SPFA(int s){
    for(int i=0; i<=n; i++) dis[i] = INF; // 初始化为无穷大
    dis[s] = 0;
    vis[s] = true; // 标记该点
    q.push(s);
    while(!q.empty()){
        int u=q.front();
        q.pop();
        for(int i=h[u]; i; i=nxt[i]){
            int v=to[i];
            if(dis[v]>dis[u]+val[i]){ // 如果可以松弛
                dis[v]=dis[u]+val[i];
                q.push(v); // 松弛后入队
            }
        }
    }
}

int main(){
    cin>>n>>m>>s;
    for(int i=1, u, v, w; i<=m; i++){
        cin>>u>>v>>w;
        add(u, v, w);
    }
    Dijkstra(s);
    SPFA(s); // 选取一个进行调用！
    for(int i=1; i<=n; i++) cout<<dis[i]<<" ";
    return 0;
}

堆优化：（可以过Luogu P4779 标准版）

#include <bits/stdc++.h>
using namespace std;
typedef long long LL;
const int maxn = 1e5+10;
const int maxm = 2e5+10;
const int INF = (1<<31)-1;
int head[maxm], vis[maxn];
LL dix[maxn];
int n, m, s, tot=0;
struct node{
    int to, nxt, d;
}edge[maxm];
struct Point { // 自定义一个小根堆
    int dd, p; // dd表示 p点到起点的距离
    bool operator <(const Point &x) const {
    return dd > x.dd;
    }
};
void add(int x, int y, int z){
    edge[tot].to = y;
    edge[tot].d = z;
    edge[tot].nxt = head[x];
    head[x] = tot++;
}
void dijkstra(){
    for(int i=1; i<=n; ++i) dix[i] = INF;
    memset(vis, 0 ,sizeof(vis));
    dix[s] = 0;
    priority_queue<Point> que;
    Point a;
    a.dd = 0; a.p = s; // 起点
    que.push(a); // 把起点放入小根堆中
    while(que.size()){
        //取出堆顶元素，也就是全局最小的 dix
        a = que.top(); que.pop();
        int x = a.p;
        if(vis[x]) continue;
        vis[x] = 1;
        //扫描 x 所有的出边
        for(int i=head[x]; i!=-1; i=edge[i].nxt){
            int y = edge[i].to;
            if(dix[y] > dix[x] + 1LL*edge[i].d) { // 当对点 y 可以被更新的时候
                dix[y] = dix[x] + 1LL * edge[i].d;
                a.dd = dix[y]; a.p = y;
                que.push(a);
            }
        }
    }
}
int main(){
    scanf("%d%d%d", &n, &m, &s);
    memset(head, -1, sizeof(head));
    while(m--){
        int x, y, z;
        scanf("%d%d%d", &x, &y, &z);
        add(x, y, z);
    }
    dijkstra();
    for(int i=1; i<n; ++i)
        printf("%lld ", dix[i]);
    printf("%lld\n", dix[n]);
    return 0;
}