求大佬看看,前四个点wa,5和6能ac

P4779 【模板】单源最短路径(标准版)

qwerfg @ 2024-03-15 21:35:06

#include<iostream>
#include<algorithm>
#include<queue>
#include<cstring>
#include<vector>
using namespace std;

typedef pair<int,int> PII;
const int N = 10e6;
int h[N],ne[N],w[N],e[N],idx;
int st[N],d[N];
int n,m,s;
priority_queue<PII , vector<PII> ,greater<PII> > heap;

void add(int a, int b, int c)
{
    e[idx] = b; w[idx] = c; ne[idx] = h[a]; h[a] = idx++;
}
void dijkstra()
{
    memset  ( d,0x3f,sizeof d);
    d[s] = 0;

    heap.push({s,0});

    while( !heap.empty())
    {
        auto t = heap.top();
        heap.pop();
        int v = t.first;int dis = t.second;

        if(st[v]) continue;
        st[v] = 1;
        for( int i = h[v] ; i != -1 ; i = ne[i])
        {
            int j = e[i];
            if( d[j] > dis + w[i])
            {
                d[j] = dis + w[i];
                heap.push({j,d[j]});
            }
        }
    }
}
int main()
{
    cin >> n >> m >> s;
    memset( h, -1 ,sizeof h);

    while( m--)
    {
        int a,b,c;
        scanf("%d%d%d",&a,&b,&c);
        add(a,b,c);
    }
    dijkstra();
    for( int i = 1; i <= n; i++) cout << d[i] << ' ';
}

by Reunite @ 2024-03-15 21:57:16

@qwerfg dij 的堆优化需要以 dis 为关键字维护小根堆,你这是把点编号丢到小根堆里去了啊。


by qwerfg @ 2024-03-15 23:31:37

@Reunite wc,谢谢大佬点悟,终于是过了


by qiuyihang @ 2024-04-03 17:39:33

@Reunite 厉害 顶一个 看了半天没看懂 STL有点怪


|