求助

堆优化+链式前向星dijkstra，不知为何WA第一个点

//

#include<iostream>
#include<iomanip>
#include<vector>
#include<queue>
#include<stack>
#include<stdio.h>
#include<cstring>
#include<string.h>
#include<cstdio>
#include<string>
#include<algorithm>
#include<utility>
#include<limits.h>
#include<map>
#include<set>
#include<cmath>
#define debug cout << "OK" << endl;
using namespace std;

//链式前向星-------------------
struct edge{
    long long to, w, nxt;
}e[500010];
int head[500010], tot;

void init()
{
    memset(head, -1, sizeof(head));
    tot = 0;
}

void add(int u, int v, long long w)
{
    e[tot].to = v, e[tot].nxt = head[u], e[tot].w = w;
    head[u] = tot++;
}
//链式前向星end-------------------

//dijkstra-------------------
long long dis[100001];

void pre()
{
    memset(dis, -1, sizeof(dis));
}
//dijkstra-------------------

//堆优化-------------------
int heap[100001], len = 0;//堆中存储点编号
int wz[100001];//wz[i]表示编号为i的点在heap中的下标

void up(int x)
{
    int u = x, v = x / 2;
    while(u != 1)
    {
        if(dis[heap[u]] < dis[heap[v]])
        {
            swap(wz[heap[u]], wz[heap[v]]);
            swap(heap[u], heap[v]);
        }
        else
        {
            break;
        }
        u = v, v = u / 2;
    }
}

void down(int x)
{
    int u = x, v = x * 2;
    while(v <= len)
    {
        if(v + 1 <= len && dis[heap[v]] > dis[heap[v + 1]])
        {
            v++;
        }
        if(dis[heap[u]] > dis[heap[v]])
        {
            swap(wz[heap[u]], wz[heap[v]]);
            swap(heap[u], heap[v]);
        }
        else
        {
            break;
        }
        u = v, v = u * 2;
    }
}

void push(int x)
{
    heap[++len] = x;
    wz[x] = len;
    up(len);
}

int pop()
{
    int ans = heap[1];
    wz[heap[1]] = -1;
    heap[1] = heap[len--];
    down(1);
    return ans;
}
//堆优化end-------------------

int n, m, s;

int main()
{
    cin >> n >> m >> s;
    init();
    for(int i = 1; i <= m; i++)
    {
        int u, v;
        long long w;
        scanf("%d %d %lld", &u, &v, &w);
        add(u, v, w);
    }
    pre();
    memset(wz, -1, sizeof(wz));
    dis[s] = 0;
    push(s);
    while(len)//全部遍历过，堆内无点
    {
        // 暴力枚举
        // int mn, u = -1;
        // for(int j = 1; j <= n; j++)
        // {
        //     if(used[j] == 0 && dis[j] != -1 && (dis[j] < mn || u == -1))
        //     {
        //         mn = dis[j], u = j;
        //     }
        // }
        // if(u == -1)
        // {
        //     break;
        // }

        //取最近的点
        int u = pop();
        if(head[u] == -1)
        {
            continue;
        }
        for(edge j = e[head[u]];; j = e[j.nxt])
        {
            if(dis[j.to] > dis[u] + j.w || dis[j.to] == -1)
            {
                //松弛
                dis[j.to] = dis[u] + j.w;

                //进堆
                if(wz[j.to] == -1)
                {
                    push(j.to);
                }
                //维护
                else
                {
                    up(wz[j.to]);
                }
            }
            if(j.nxt == -1)
            {
                break;
            }
        }
    }
    for(int i = 1; i <= n; i++)
    {
        printf("%lld ", dis[i]);
    }
    cout << endl;
    return 0;
}