最短路 + 邻接表 + 堆优化（模板）（Dijkstra + SPFA）

秒速五厘米 2022-06-07 12:50 154阅读 0赞

--------------------

**模板已经过题目验证**

--------------------

最短路模板+邻接表建图+堆优化(优先队列) 复杂度O(Elog(E))

#include<iostream> 
    #include<queue> 
    #include<vector> 
    #include<cstdio> 
    
    using namespace std;  
    
    const int maxn = 100005;   
    const int inf = 1<<29;
    int dis[maxn];  
    int n, m, s;  
    
    struct edge {
       int to,cost;}; 
    
    vector<edge> G[maxn];  
    
    struct node {  
        int len, v;  
        friend bool operator <(node x, node y) {  
            return x.len > y.len;  
        }  
    };  
    
    void Dijkstra() {  
        priority_queue<node> q;  
        fill(d, d+maxn, inf);
        dis[s]=0; node t;  
        t.len=0; t.v=s;  
        q.push(t);  
        while(q.size()) {  
            t = q.top(); q.pop();  
            if(dis[t.v] < t.len) continue;  
            for(int i = 0; i < G[t.v].size(); i++) {  
                edge e = G[t.v][i];  
                if(dis[e.to] > dis[t.v] + e.cost) {  
                    dis[e.to] = dis[t.v] + e.cost;  
                    node temp = {dis[e.to], e.to};  
                    q.push(temp);  
                }  
            }  
        }  
    }  
    int main() {  
        while(~scanf("%d %d", &n, &m), (n+m)) {  
            for(int i = 0; i <= n; i++) G[i].clear();  
            for(int i = 1; i <= m; i++) {  
                int a, b, w;  
                edge t, rt;  
                scanf("%d %d %d", &a, &b, &w);  
                t.to=b; t.cost=w;  
    // rt.to=a; rt.cost=w; //双向 
                G[a].push_back(t);  
    // G[b].push_back(rt); 
            }  
            s = 1; //起点 
            Dijkstra();  
            cout << dis[n] << endl;  
        }  
        return 0;  
    }  
    //const inline int read() { //这是快速输入 用法为 int a = read();
    // int k=0,f=1; char c=getchar();
    // for(;!isdigit(c);c=getchar())
    // if(c=='-') f=-1;
    // for(;isdigit(c);c=getchar())
    // k=k*10+c-'0';
    // return k*f;
    //}

--------------------

最短路模板+邻接表建图+SPFA

#include<iostream> 
    #include<queue> 
    #include<vector> 
    #include<cstdio> 
    
    using namespace std;  
    
    const int maxn = 100005;   
    const int inf = 1<<29;
    
    struct edge{
       int to, cost;};  
    int dis[maxn], vis[maxn];  
    
    int n, m, s;  
    vector<edge> G[maxn];  
    
    void SPFA() {  
        fill(dis, dis+maxn, inf);
        dis[s] = 0;  
        fill(vis, vis+maxn, 0);  
        queue<int> q;  
        q.push(s);  
        while(!q.empty()) {  
            int u = q.front();  
            q.pop();  
            vis[u] = 0;  
            for(int i = 0; i < G[u].size(); i++) {  
                int v=G[u][i].to, len=G[u][i].cost;  
                if(dis[v] > dis[u] + len) {  
                    dis[v] = dis[u] + len;  
                    if(vis[v] == 0) {  
                        vis[v] = 1;  
                        q.push(v);  
                    }  
                }  
            }  
        }  
    }  
    int main() {  
        while(~scanf("%d %d", &n, &m), (n+m)) {   
            for(int i = 0; i <= n; i++) G[i].clear();  
            for(int i = 0; i < m; i++) {  
                int a, b, w;  
                edge t, rt;  
                scanf("%d %d %d", &a, &b, &w);  
                t.to=b; t.cost=w;  
    // rt.to=a; rt.cost=w; //双向 
                G[a].push_back(t);  
    // G[b].push_back(rt); 
            }  
            s = 1;  
            SFPA();  
            cout << dis[n] << endl;  
        }  
        return 0;  
    }  
    //const inline int read() { //这是快速输入 用法为 int a = read();
    // int k=0,f=1; char c=getchar();
    // for(;!isdigit(c);c=getchar())
    // if(c=='-') f=-1;
    // for(;isdigit(c);c=getchar())
    // k=k*10+c-'0';
    // return k*f;
    //}