算法模板

本文主要是介绍算法模板，对大家解决编程问题具有一定的参考价值，需要的程序猿们随着小编来一起学习吧！

单源最短路径 dijkstra

#include<bits/stdc++.h>
using namespace std;

const int N=1e6;
int n,m,s,dis[N], vis[N];

struct T{
    int v,w;
};
vector<T> G[N];

void add(int u, int v, int w){
    T temp;
    temp.v = v;
    temp.w = w;
    G[u].push_back(temp);
}

void add2(int u, int v, int w){
    add(u, v, w);
    add(v, u, w);
}

void print(){//图的打印 
    for(int i=1; i<=n; i++){
        cout<<i<<" : ";
        for(int j=0; j<G[i].size(); j++){
            cout<<G[i][j].v<<" "<<G[i][j].w<<"; ";
        }cout<<endl;
    }
}

void dijkstra(int s){
//    fill(dis, dis+N, INT_MAX);   //将 dis初始化为 INT_MAX 
    memset(dis, 0x3f, sizeof(dis));//将 dis的每个字节位都初始化为 0x3f, vis[i]=0x3f3f3f3f
    memset(vis, 0, sizeof(vis));   //将 vis初始化为 0
    dis[s]=0;
    for(int i=1; i<=n; i++){
        int minn=INT_MAX, u=i;
        for(int j=1; j<n; j++){ //这里一步，如果使用链式向前星会发生变化 
            if(minn>dis[j] && !vis[j]){
                minn=dis[j], u=j;
            }
        }
        if(!u) break;//u点访问过了 
        vis[u]=1;
        for(int j=0; j<G[u].size(); j++){
            T temp = G[u][j];
            int v = temp.v, w=temp.w;
            if(dis[u]+w < dis[v]){
                dis[v] = dis[u]+w;
            }
        }
    }
}

//P3371 【模板】单源最短路径（弱化版）
int main(){
    freopen("data.in", "r", stdin); 
    cin>>n>>m>>s;
    for(int i=1; i<=m; i++){
        int u, v, w; cin>>u>>v>>w;
        add(u, v, w);
    }
//    print();
    dijkstra(s);
    for(int i=1; i<=n; i++) cout<<dis[i]<<" ";
    return 0;
}

这篇关于算法模板的文章就介绍到这儿，希望我们推荐的文章对大家有所帮助，也希望大家多多支持为之网！