图论--最短路-- Dijkstra模板（目前见到的最好用的）

#include<bits/stdc++.h>
using namespace std;
typedef long long ll;
typedef pair<int,int> PII;
struct Node
{
    int var,next,val;
} edge[100000005];
int head[100005],tot,dis[100005],N,M;
bool vis[100005];
priority_queue<PII> Q;
void add(int a, int b, int c)
{
    edge[++tot].var = b;
    edge[tot].val = c;
    edge[tot].next = head[a];
    head[a] = tot;
}
void init()//多组输入调用
{
    tot=0;
    memset(head,0,sizeof(head));
}
void dijkstra(int s)
{
    memset(dis,0x3f,sizeof(dis));
    //memset(vis,0,sizeof(vis));
    //while(Q.size()) Q.pop();
    dis[s] = 0;
    Q.push(make_pair(0,s));
    while(!Q.empty())
    {
        int x=Q.top().second;
        Q.pop();
        if(vis[x])continue;
        vis[x]=1;
        for(int i=head[x]; i; i=edge[i].next)
        {
            int y=edge[i].var;
            if(dis[x]+edge[i].val<dis[y])
            {
                dis[y]=dis[x]+edge[i].val;
                if(!vis[y])
                Q.push(make_pair(-dis[y],y));
            }
        }

    }
}
int main()
{
    int S;
    scanf("%d %d %d",&N,&M,&S);
    while(M--)
    {
        int x,y,z;
        scanf("%d %d %d",&x,&y,&z);
        add(x,y,z);
    }
    dijkstra(S);
    for(int i=1; i<=N; i++)printf("%d ",dis[i]);
}