问题标题: 算法模板（8个）分享

最短路径算法模板（8个）大甩卖！

包括：

Dijkstra堆优化

Kruscal

欧拉路径

哈密尔顿回路

Ford

拓扑排序

Prim

SPFA

的标准模板！

适用人群：手残党、要在课上默写模板的、学过的&能看懂的

用法用量：天天看，背会就行了

售价：10豆

获取方式：仅限洛谷私聊

会持续更新！

黄中阳在2022-05-22 22:19:26追加了内容

手滑，是图论算法

黄中阳在2022-05-22 22:26:49追加了内容

不卖了不卖了：
 

Dijkstra堆优化

#include<iostream>
#include<cstring>
#include<queue>
#define MAXN 505
using namespace std;
typedef pair<int,int> P; 
int n,m,st;
struct edge{
    int next,w;
};
vector<edge> g[MAXN];
int dis[MAXN];
priority_queue<P,vector<P>,greater<P> > q; 
void dijkstra(int st){
    memset(dis,0x3f,sizeof(dis));
    dis[st]=0;
    q.push(P(0,st));
    while(!q.empty()){
        P tmp=q.top(); q.pop();
        int u=tmp.second;
        if(dis[u]<tmp.first) continue;
        for(int i=0;i<g[u].size();i++){
            edge e=g[u][i];
            if(dis[e.next]>dis[u]+e.w){
                dis[e.next]=dis[u]+e.w;
                q.push(P(dis[e.next],e.next));
            }
        }
    }
}
int main(){
    cin>>n>>m>>st;
    for(int i=1,u,v,w;i<=m;i++){
        cin>>u>>v>>w;
        g[u].push_back((edge){v,w});
    }
    dijkstra(st);
    for(int i=1;i<=n;i++){
        if(dis[i]==0x3f3f3f3f) cout<<-1<<" ";
        else cout<<dis[i]<<" ";
    }
    return 0;
}

Kruscal

#include<iostream>
#include<algorithm>
#define MAXN 10005
using namespace std;
int n,m,cnt,ans;
int fa[10005];
struct node{
    int u,v,w;
}a[MAXN];
void init(){
    for(int i=1;i<=n;i++)
        fa[i]=i;
} 
int find(int x){
    if(x==fa[x]) return x;
    return fa[x]=find(fa[x]);
}
void unite(int x,int y){
    x=find(x); y=find(y);
    if(x==y) return ;
    fa[x]=y;
}
bool same(int x,int y){
    return find(x)==find(y);
}
bool cmp(node x,node y){
    return x.w<y.w;
}
int main(){
    cin>>n>>m;
    for(int i=1;i<=m;i++){
        cin>>a[i].u>>a[i].v>>a[i].w;
    }
    init();
    sort(a+1,a+1+m,cmp);
    for(int i=1;i<=m;i++){
        if(!same(a[i].u,a[i].v)){
            unite(a[i].u,a[i].v);
            cnt++;
            ans+=a[i].w;
        }
        if(cnt==n-1)
            break;
    }  
    cout<<ans;
    return 0;
}
欧拉路径

#include<iostream>
#define MAXN 1005
using namespace std;
int n,m,cnt;
int g[MAXN][MAXN];
int d[MAXN];
int ans[MAXN];
void dfs(int pos){
    for(int i=1;i<=n;i++){
        if(g[pos][i]){
            g[pos][i]--;
            g[i][pos]--;
            dfs(i);
        }
    }
    ans[++cnt]=pos;
    return ;
}
int main(){
    cin>>n>>m;
    for(int i=1,u,v;i<=m;i++){
        cin>>u>>v;
        g[u][v]++;
        g[v][u]++;
        d[u]++,d[v]++;
    }
    int st=1;
    for(int i=1;i<=n;i++){
        if(d[i]%2==1){
            st=i;
            break;
        }
    }
    dfs(st);
    for(int i=cnt;i>=1;i--)
        cout<<ans[i]<<" ";
    return 0;
} 





哈密尔顿回路

#include<iostream>
#define MAXN 505
using namespace std;
int n,m,cnt;
int g[MAXN][MAXN];
bool vis[MAXN];
int ans[MAXN];
bool dfs(int x,int t){
    if(t>n){
        if(g[x][1])
            return 1;
        return 0;
    }
    for(int i=1;i<=n;i++){
        if(g[x][i]&&!vis[i]){
            vis[i]=1;
            ans[t]=i;
            if(dfs(i,t+1))
                return 1;
            vis[i]=0;
        }
    }
    return 0;
}
int main(){
    cin>>n>>m;
    for(int i=1,u,v;i<=m;i++){
        cin>>u>>v;
        g[u][v]++,g[v][u]++;
    }
    vis[1]=1;
    ans[1]=1;
    if(dfs(1,2)){
        for(int i=1;i<=n;i++){
            cout<<ans[i]<<" ";
        }
        cout<<ans[1]<<endl;
    }
    else{
        cout<<"NO";
    }
    return 0;
}







Ford

#include<iostream>
#include<cstring>
#include<queue>
#include<vector>
#define MAXN 1005
using namespace std;
int dis[MAXN];
int n,m;
struct edge{
    int next,w;
}; 
vector<edge> g[MAXN];
bool ford(int st){
    memset(dis,0x3f,sizeof(dis));
    dis[st]=0;
    for(int t=1;t<n;t++){
        for(int i=1;i<=n;i++){
            for(int j=0;j<g[i].size();j++){
                edge e=g[i][j];
                if(dis[e.next]>dis[i]+e.w){
                    dis[e.next]=dis[i]+e.w;
                }
            }
        }
    }
    for(int i=1;i<=n;i++){
        for(int j=0;j<g[i].size();j++){
            edge e=g[i][j];
            if(dis[e.next]>dis[i]+e.w){
                return 0;
            }
        }
    }
    return 1;
}








拓扑排序

#include<iostream>
#include<queue>
#define MAXN 505
using namespace std;
int n,m,cnt;
vector<int> g[MAXN];
int in[MAXN];
int top[MAXN];
queue<int> q;//队列维护入度为0的点
void Topsort(){
    for(int i=1;i<=n;i++){
        if(in[i]==0)
            q.push(i);
    }
    while(!q.empty()){
        int u=q.front(); q.pop();
        top[++cnt]=u;
        for(int i=0;i<g[u].size();i++){
            int v=g[u][i];
            in[v]--;
            if(in[v]==0)
                q.push(v);
        }
    }
} 
int main(){
    cin>>n>>m;
    for(int i=1,u,v;i<=m;i++){
        cin>>u>>v;
        g[u].push_back(v);
        in[v]++;
    }
    Topsort();
    for(int i=1;i<=n;i++)
        cout<<top[i]<<" ";
    return 0;
}
Prim

int MST_prim(){
    int ans=0;
    memset(dis,0x3f,sizeof(dis));
    memset(found,false,sizeof(found));
    dis[1]=0;
    while(1){
        int u=-1;
        for(int i=0;i<=n;i++){
            if(!found[i]&&(u==-1||dis[i]<dis[u])){
                u=i;
            }
        }
        if(u==-1) break;
        found[u]=true;
        ans+=dis[u];
        for(int i=0;i<=n;i++){
            if(!found[i]&&g[u][i]<dis[i]){
                dis[i]=g[u][i];
            }
        }
    }
    return ans;
}
SPFA

#include<iostream>
#include<cstring>
#include<queue>
#define MAXN 1005
using namespace std;
int n,m;
struct edge{
    int next,w;
};
vector<edge> g[MAXN];
queue<int> q;
int dis[MAXN];
bool vis[MAXN];
void spfa(int st){
    memset(dis,0x3f,sizeof(dis));
    dis[st]=0;
    q.push(st);
    vis[st]=1;
    while(!q.empty()){
        int u=q.front(); q.pop();
        vis[u]=0;
        for(int i=0;i<g[u].size();i++){
            edge e=g[u][i];
            if(dis[e.next]>dis[u]+e.w){
                dis[e.next]=dis[u]+e.w;
                if(!vis[e.next]){
                    q.push(e.next);
                    vis[e.next]=1;
                }
            }
        }
    }
}

麻烦顺便挑挑可有错