68pts求助

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

aaalys @ 2024-06-23 15:47:04

#include <iostream>
#include <queue>
#include <algorithm>
#include <vector>
using namespace std;
typedef long long ll;
const ll inf = (1ll << 31) - 1;

struct node{
    ll v , w;
};
vector<node>e[100010];
ll d[100010];
bool vis[100010];
struct cmp{
    bool operator()(int a ,int b){return d[a] > d[b];}
};
priority_queue<int , vector<int> , cmp>q;
int main()
{
    int n , m , s;
    cin >> n >> m >> s;
    for (int i = 1; i <= m; i++){
        int u , v , w;
        cin >> u >>  v >> w;
        e[u].push_back(node{v , w});
    }
    for (int i = 0; i <= n; i++)d[i] = inf;
    d[s] = 0;
    q.push(s);
    while (!q.empty()){
        int fr = q.top();
        q.pop();
        //cout << fr << endl;
        if (vis[fr])continue;
        vis[fr] = true;
        for (node i:e[fr]){
            ll v = i.v , w = i.w;
            //if (vis[v])continue;
            if (d[v] > d[fr] + w){
                d[v] = d[fr] + w;
                if (!vis[v])q.push(v);
            }
        }
    }
    for (int i = 1; i <= n; i++)cout << d[i] << ' ';
    return 0;
}

WA on#1,#4


by DYH66 @ 2024-06-23 17:18:36

https://www.luogu.com.cn/record/162939098


by DYH66 @ 2024-06-23 17:19:34

d的值改变后堆不会实时更新


by DYH66 @ 2024-06-23 17:25:25

@aaalys 我觉得应该是这样的手写堆应该不会


by aaalys @ 2024-06-23 19:58:44

@DYH66 那我应该怎么改?


|