ZZQ's Blog

#include <iostream>
#include <stdio.h>
#include <stdlib.h>
#include <vector>
#include <set>
#include <map>
#include <time.h>
using namespace std;
int n,dist[1000001],cn[1000001];
struct scmp
{
    bool operator () (int a,int b)
    {
        if(dist[a]!=dist[b]) return dist[a]<dist[b]; else return a<b; 
    }
};
vector<int> vb[1000001],vv[1000001];
set<int,scmp> qs;
void dijkstra(int s)
{
    for(int i=1;i<=n;i++) dist[i]=0x7ffffff;
    dist[s]=0;
    for(int i=1;i<=n;i++) qs.insert(i);
    while(!qs.empty())
    {
        int u=*qs.begin();
        qs.erase(u);
        for(int i=0;i<cn[u];i++)
        {
            int v=vb[u][i],vx=vv[u][i];
            if(dist[v]>dist[u]+vx)
            {
                qs.erase(v);
                dist[v]=dist[u]+vx;
                qs.insert(v);
            }
        }
    }
}
int main()
{
    int m,a,b,c;
    scanf("%d %d",&n,&m);
    for(int i=1;i<=m;i++)
    {
        scanf("%d%d%d",&a,&b,&c);
        cn[a]++;
        vb[a].push_back(b);
        vv[a].push_back(c);
    }
    dijkstra(1);
    for(int i=1;i<=n;i++) printf("%d ",dist[i]);
}