WA#6

#include<iostream>
#include<queue>
#include<cstring>

using namespace std;

typedef long long LL;
typedef pair<int, int> PII;

const int N = 3e5+10, M = 2*N;

int e[M], ne[M], h[M], w[M], idx;

bool st[N];
int n, m;
LL d[N];

void add(int a, int b, LL c)
{
    e[idx] = b, ne[idx] = h[a], w[idx] = c, h[a] = idx++;
}

void djstra()
{
    for(int i = 1; i<=n; i++)   d[i] = 1e18;
    d[1] = 0;
    
    priority_queue<PII, vector<PII>, greater<PII>> p;//小顶堆
    p.push({0, 1});
    
    while(p.size())
    {
        auto t = p.top();
        p.pop();//弹出这个元素
        
        int a = t.second;//a表示节点号，b表示节点距离源点的距离
        
        if(st[a])  continue;//如果最短路已经确定，那么直接跳过
        st[a] = true;//更新状态
        
        for(int i = h[a]; i != -1; i = ne[i])
        {
            int j = e[i];
            if(st[j])   continue;
            if(d[j] > d[a] + w[i])
            {
                d[j] = d[a] + w[i];
                p.push({d[j], j});
            }
        }
    }
    
}

int main()
{
    
    memset(h, -1, sizeof h);
    
    scanf("%d%d", &n, &m);
    
    while(m--)
    {
        int a, b;
        LL c;
        scanf("%d%d%lld",&a, &b, &c);
        add(a, b, c);
    }
    
    djstra();
    
    for(int i = 1; i<=n; i++)
    {
        if(d[i] == 0x3f3f3f3f)
            printf("-1 ");
        else
            printf("%lld ", d[i]);
    }
    
    return 0;
}