1 条题解

  • 2
    @ 2023-10-21 09:38:15

    本题解同时包含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;
    }
    
  • 1

【模板】单源最短路(Dijkstra / SPFA)

信息

ID
1023
难度
1
分类
图结构 | 最短路 点击显示
标签
递交数
10
已通过
2
通过率
20%
上传者