dijkstra模板

输入：

4 6 1
1 2 2
2 3 2
2 4 1
1 3 5
3 4 3
1 4 4

输出：

0 2 4 3

堆优化版本

#include<bits/stdc++.h>
using namespace std;
#define debug(x) cout<<"# "<<x<<" "<<endl;
typedef long long ll;
const ll mod=2147483647000;
const ll N=500007;
struct Edge
{
    ll v,w,next;//v:目的地,w:距离,next:下一个节点
}G[N];
ll head[N],cnt,n,m,s;
ll dis[N];//存距离
inline void addedge(ll u,ll v,ll w)//链式前向星存图
{
    cnt++;
    G[cnt].w=w;
    G[cnt].v=v;
    G[cnt].next=head[u];
    head[u]=cnt;
}
struct node
{
    ll d,u;//d是距离u是起点
    bool operator<(const node& t)const//重载运算符
    {
        return d>t.d;
    }
};
inline void Dijkstra()
{
    for(register int i=1;i<=n;++i)dis[i]=mod;//初始化
    dis[s]=0;
    priority_queue<node>q;//堆优化
    q.push((node){0,s});//起点push进去
    while(!q.empty())
    {
        node tmp=q.top();q.pop();
        ll u=tmp.u,d=tmp.d;
        if(d!=dis[u])continue;//松弛操作剪枝
        for(register int i=head[u];i;i=G[i].next)//链式前向星
        {
            ll v=G[i].v,w=G[i].w;
            if(dis[u]+w<dis[v])//符合条件就更新
            {
                dis[v]=dis[u]+w;
                q.push((node){dis[v],v});//沿着边往下走
            }
        }
    }
}
int main()
{
    scanf("%lld %lld %lld",&n,&m,&s);
    for(register int i=1;i<=m;++i)
    {
        ll x,y,z;
        scanf("%lld %lld %lld",&x,&y,&z);
        addedge(x,y,z);//建图
    }
    Dijkstra();
    for(register int i=1;i<=n;++i)
        printf("%lld ",dis[i]);
    printf("\n");
    return 0;
}