【模板】Dijkstra

#include<bits/stdc++.h>
using namespace std;
int n,m,s;
long long dis[10002];
bool flag[10002];
struct Edge
{
    int id;
    long long c;
    bool operator <(const Edge &r)const
    {
        return c>r.c;
    }
    Edge(int x,long long y)
    {
        id=x;
        c=y;
    }
};
vector<Edge>G[10002];
void Dij(int s)
{
    for(int i=1;i<=n;i++)
    {
        flag[i]=0;
        dis[i]=0x7fffffff;
    }
    dis[s]=0;
    priority_queue<Edge>q;
    q.push(Edge(s,0));
    while(!q.empty())
    {
        Edge Te=q.top();
        q.pop();
        int u=Te.id;
        if(flag[u])continue;
        flag[u]=1;
        for(int i=0;i<G[u].size();i++)
        {
            int v=G[u][i].id;
            if(!flag[v]&&dis[v]>dis[u]+G[u][i].c)
			{
				dis[v]=dis[u]+G[u][i].c;
				q.push(Edge(v,dis[v]));
			}
        }
    }
}
int main()
{
    int a,b,c;
    scanf("%d%d%d",&n,&m,&s);
    for(int i=1;i<=m;i++)
    {
        scanf("%d%d%d",&a,&b,&c);
        G[a].push_back(Edge(b,c));
    }
    Dij(s);
    for(int i=1;i<=n;i++)printf("%lld ",dis[i]);
    return 0;
}