最短路合辑

Dijkstra算法，堆优化版本复杂度是mlog(m)。适合于没有负权的图。

#include <bits/stdc++.h>

using namespace std;

using LL = long long;

const int N  = 1e5 + 5;

const int INF = 0x3f3f3f3f;

vector<pair<int,int>> G[N];

int vis[N];
int dist[N];

void dij(int s){
    memset(vis,0,sizeof(vis));
    memset(dist,INF,sizeof(dist));

    priority_queue<pair<int,int>> q;
    q.push({0, s});
    dist[s]=0;
    while(!q.empty()){
        auto u = q.top().second;
        q.pop();

        if(vis[u])continue;
        vis[u]=1;

        for(auto &e:G[u]){
            int v=e.first;
            int w=e.second;
            if(dist[u] + w < dist[v]){
                dist[v] = dist[u] + w;
                q.push(make_pair(-(dist[u] + w), v));
            }
        }
    }    
}

int n, m, src;

int main(){
    cin >> n >> m >> src;
    for(int i=0;i<m;++i){
        int x, y, w;
        cin >> x >> y >> w;
        G[x].push_back(make_pair(y,w));
        G[y].push_back(make_pair(x,w));
    }

    dij(src);
    for(int i=1;i<=n;++i){
        if(dist[i] < 1e8) cout<<dist[i]<<" ";
        else cout<<"-1 ";
    }

    
    return 0;
}

这个题目能让dijkstra的理解深刻一点（主要是它的正确性）。https://leetcode.cn/problems/path-with-maximum-probability/

Bellman_ford算法，复杂度O(n*m)。适用于有负权的情况。复杂度高。

#include <bits/stdc++.h>

using namespace std;

using LL = long long;

const int N  = 1e5 + 5;

const int INF = 0x3f3f3f3f;

vector<pair<int,int>> G[N];

int dist[N];

int n, m, src;

int bellman_ford(int s){
    memset(dist,INF,sizeof(dist));
    dist[s]=0;

    for(int i=1;i<n;++i){ //n-1轮更新
        for(int u=1;u<=n;++u){
            if(dist[u]==INF){continue;}
            for(auto& p:G[u]){
                int v=p.first, w=p.second;
                if(dist[v]>dist[u]+w){
                    dist[v]=dist[u]+w;
                }
            }
        }
    }

    for(int u=1;u<=n;++u){
        for(auto& p:G[u]){
            int v=p.first, w=p.second;
            if(dist[v]>dist[u]+w){
                dist[v]=dist[u]+w; // n轮之后还能更新
                return 0;
            }
        }
    }

    return 1;    
}

int main(){
    cin >> n >> m >> src;
    for(int i=0;i<m;++i){
        int x, y, w;
        cin >> x >> y >> w;
        G[x].push_back(make_pair(y,w));
    }

    bellman_ford(src);
    for(int i=1;i<=n;++i){
        if(dist[i] < 1e8) cout<<dist[i]<<" ";
        else cout<<"-1 ";
    }
    return 0;
}

SPFA算法。最差复杂度与bellman ford一样。但是最好复杂度是O(M)。

#include <bits/stdc++.h>

using namespace std;

using LL = long long;

const int N  = 1e5 + 5;

const int INF = 0x3f;

int dist[N], inq[N];

int n, m, src;

int head[N], nxt[N], to[N], weight[N];
int cnte=0;

int neg_loog[N];

void add_edge(int x, int y, int w){
    to[++cnte]=y;
    weight[cnte]=w;
    nxt[cnte]=head[x];
    head[x]=cnte;
}

int spfa(int s){ // return 0 if neg loop;    
    queue<int> q;
    q.push(s);
    dist[s]=0;
    inq[s]=1;
    neg_loog[1]=1;
    while(!q.empty()){
        int u=q.front();
        q.pop();
        inq[u]=0;

        for(int e=head[u];e;e=nxt[e]){
            int v=to[e], w=weight[e];
            if(dist[v]>dist[u]+w){
                dist[v]=dist[u]+w;
                if(!inq[v]){
                    if(++neg_loog[v]>=n){ //某一个点入队n次及以上，就是有负环。
                        return 0;
                    }
                    inq[v]=1;
                    q.push(v);
                }
            }
        }
    }
    return 1;
}

void init(){
    cnte=0;
    memset(head,0,sizeof(head));
    memset(neg_loog,0,sizeof(neg_loog));
    memset(dist,INF,sizeof(dist));
    memset(inq,0,sizeof(inq));

}

int main(){
    int t;cin>>t;
    while(t--){
        cin >> n >> m;
        src=1;
        init();
        for(int i=0;i<m;++i){
            int x, y, w;
            cin>>x>>y>>w;
            if(w<0){
                add_edge(x, y, w);
            }
            else{
                add_edge(x, y, w);
                add_edge(y, x, w);
            }
        }

        if(!spfa(src)){
            cout<<"YES"<<endl;
        }else{
            cout<<"NO"<<endl;
        }
    }
   
    return 0;
}

floyd算法。复杂度O(N^ 3)，只需要记得要先枚举中间节点。