标准dijkstra

#include<bits/stdc++.h>
using namespace std;

const int Max_n=100010,Max_m=200010,Max_int=2147483647;

struct Edge
{
    int to;
    int len;
    int next;
}edge[Max_m];

int n,m,s,now,mn;
int arrive,leave,length,num;
int ans[Max_n],last[Max_n];
bool Visit[Max_n];

void input(int a,int b,int c)
{
    num++;
    edge[num].to=b;
    edge[num].len=c;
    edge[num].next=last[a];
    last[a]=num;
}

int main()
{
    cin>>n>>m>>s;
    for(int i=1;i<=n;i++) ans[i]=2147483647;
    for(int i=0;i<m;i++)
    {
        cin>>arrive>>leave>>length;
        input(arrive,leave,length);
    }
    
    int now=s;
    ans[s]=0;
    while(!Visit[now])
    {
        Visit[now]=true;
        for(int i=last[now];i!=0;i=edge[i].next)
        {
            if(!Visit[edge[i].to] && ans[edge[i].to]>ans[now]+edge[i].len)
                ans[edge[i].to]=ans[now]+edge[i].len;
        }
        mn=Max_int;
        for(int i=1;i<=n;i++)
            if(!Visit[i] && mn>ans[i])
            {
                mn=ans[i];
                now=i;
            }
    }
    
    for(int i=1;i<=n;i++) cout<<ans[i]<<' ';
    return 0;
}