第一次用Markdown编辑器写博文呢。

单源最短路的模板，链式前向星写法。

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

Dijkstra

#include
    
     using namespace std;const int INF=0x3f3f3f3f;/* begin 链式前向星 */const int MAXN=1000010;const int MAXM=2000010;struct Edge{    int v,w,next;    Edge(int v=0,int w=0):v(v),w(w){}};int cnt_edge;int head[MAXN+5];Edge edge[MAXM+5];inline void init_graph(int n){    cnt_edge=0;    memset(head+1,0,sizeof(head[0])*n);}inline void add_edge(int u,int v,int w){    cnt_edge++;    edge[cnt_edge].v=v;    edge[cnt_edge].w=w;    edge[cnt_edge].next=head[u];    head[u]=cnt_edge;}/* end 链式前向星 *//* begin Dijkstra */bool vis[MAXN+5];int dis[MAXN+5];struct Edge_node{    int v,w;    Edge_node(int v=0,int w=0):v(v),w(w){}    bool operator<(const Edge_node &e)const {        return w>e.w;    }};void Dijkstra(int n,int s){    memset(vis+1,0,sizeof(vis[0])*n);    for(int i=1;i<=n;i++) dis[i]=INF;    priority_queue
     
       pq;    dis[s]=0;    pq.push(Edge_node(s,0));    while(!pq.empty()){        int u=pq.top().v;        pq.pop();        if(vis[u])continue;        vis[u]=1;        for(int i=head[u];i;i=edge[i].next){            int &v=edge[i].v;            int &w=edge[i].w;            if(!vis[v]&&dis[v]>dis[u]+w){                dis[v]=dis[u]+w;                pq.push(Edge_node(v,dis[v]));            }        }    }}/* end Dijkstra */int main(){    int n,m,s;    while(~scanf("%d%d%d",&n,&m,&s)){        init_graph(n);        for(int i=1;i<=m;i++){            int u,v,w;            scanf("%d%d%d",&u,&v,&w);            add_edge(u,v,w);        }        Dijkstra(n,s);        for(int i=1;i<=n;i++){            printf("%d%c",dis[i]," \n"[i==n]);        }    }}