模板 - 图论 - 单源最短路

第一次用Markdown编辑器写博文呢。
单源最短路的模板，链式前向星写法。

非负权的单源最短路Dijkstra算法。

Dijkstra

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

const int INF=0x3f3f3f3f;
const int MAXN=1000010;
const int MAXM=500000;
struct qnode{
    int v;
    int c;
    qnode(int v=0,int c=0):v(v),c(c){}
    bool operator<(const qnode &r)const {
        return c>r.c;
    }
};

struct Edge{
    int v,cost,next;
    Edge(int v=0,int cost=0):v(v),cost(cost){}
};

Edge E[MAXM];
int H[MAXN];

int top;
void addedge(int u,int v,int w){
    E[top].v=v;
    E[top].cost=w;
    E[top].next=H[u];
    H[u]=top;
}

bool vis[MAXN];
int dist[MAXN];

void Dijkstra(int n,int start){
    memset(vis,false,sizeof(vis));
    for(int i=1;i<=n;i++)dist[i]=INF;
    priority_queue<qnode> que;
    while(!que.empty())que.pop();
    dist[start]=0;
    que.push(qnode(start,0));
    qnode tmp;
    while(!que.empty()){
        tmp=que.top();
        que.pop();
        int u=tmp.v;
        if(vis[u])continue;
        vis[u]=true;
        for(int i=H[u];i;i=E[i].next){
            int v=E[i].v;
            int cost=E[i].cost;
            if(!vis[v]&&dist[v]>dist[u]+cost){
                dist[v]=dist[u]+cost;
                que.push(qnode(v,dist[v]));
            }
        }
    }
}



int main(){
    int n,m,s;
    while(~scanf("%d%d%d",&n,&m,&s)){
        top=0;
        memset(H,0,sizeof(H));
        for(int i=1;i<=m;i++){
            int u,v,w;
            scanf("%d%d%d",&u,&v,&w);
            ++top;
            addedge(u,v,w);
        }
        Dijkstra(n,s);
        for(int i=1;i<=n;i++){
            printf("%d%c",dist[i]>=0x3f3f3f3f?2147483647:dist[i]," \n"[i==n]);
        }
    }
}

模板 - 图论 - 单源最短路

原文：https://www.cnblogs.com/Yinku/p/10575322.html