Dijkstra+堆优化

图论综合
洛谷题目传送门

#include<iostream>
#include<cstdlib>
#include<cstdio>
#include<cmath>
#include<cstring>
#include<iomanip>
#include<algorithm>
#include<ctime>
#include<queue>
#include<stack>
#include<vector>
#define rg register
#define il inline
#define lst long long
#define ldb long double
#define N 10050
#define M 500050
using namespace std;
const int Inf=2147483647;
int n,m,S,cnt;
struct EDGE{
    int to,nxt,v;
}ljl[M];
int hd[N];
lst dis[N],vis[N];
struct cmp{
    bool operator()(int x,int y)
        {
            return dis[x]>dis[y];
        }
};
priority_queue <int,vector<int>,cmp> Q;
il int read()
{
    rg int s=0,m=0;rg char ch=getchar();
    while(ch<'0'||ch>'9'){if(ch=='-')m=1;ch=getchar();}
    while(ch>='0'&&ch<='9')s=(s<<3)+(s<<1)+(ch^48),ch=getchar();
    return m?-s:s;
}
il void Dijkstra()
{
    for(rg int i=1;i<=n;++i)dis[i]=Inf;
    while(!Q.empty())Q.pop();
    Q.push(S),dis[S]=0;
    while(!Q.empty())
    {
        rg int now=Q.top();
        Q.pop();
        if(!vis[now])
        {
            vis[now]=1;
            for(rg int i=hd[now];i;i=ljl[i].nxt)
            {
                rg int qw=ljl[i].to;
                dis[qw]=min(dis[qw],dis[now]+ljl[i].v);
                Q.push(qw);
            }
        }
    }
}
int main()
{
    n=read(),m=read(),S=read();
    for(rg int i=1;i<=m;++i)
    {
        rg int p=read(),q=read(),o=read();
        ljl[++cnt]=(EDGE){q,hd[p],o},hd[p]=cnt;
    }
    Dijkstra();
    for(rg int i=1;i<=n;++i)
        printf("%lld ",dis[i]);
    puts("");
    return 0;
}