求助链式前向星写法

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

Dino_chx @ 2022-11-14 17:00:57

最近学会链式前向星然后来写dijkstra结果16分TAT。dalao们帮我看看呗

#include<bitset>
#include<queue>
#include<iostream>
#include<cstring>
#include<cstdio>
#define inf 2147483647
using namespace std;
const int N = 1e6 + 10;
struct Edge {
    int to, w, next;
} edge[N];
struct PE {
    int to, dis;
    bool operator<(const PE &e)const {
        return dis < e.dis;
    }
};
int cntEdge, head[N], dist[N];
bitset<N> vis;
void insert(int u, int v, int w) {
    edge[++cntEdge].to = v;
    edge[cntEdge].w = w;
    edge[cntEdge].next = head[u];
    head[u] = cntEdge;
    return;
}
int n, m, starter;
priority_queue<PE> q;
void dijkstra() {
    for (int i = 0; i <= n; i++) {
        dist[i] = inf;
    }
    dist[starter] = 0;
    q.push((PE){starter, dist[starter]});
    while (!q.empty()) {
        PE top = q.top();
        q.pop();
        int x = top.to;
        if (vis[x])
            continue;
        vis[x] = 1;
        for (int i = head[x]; i; i = edge[i].next) {
            int to = edge[i].to, w = edge[i].w;
            if (dist[x] + w < dist[to]) {
                dist[to] = dist[x] + w;
                if (!vis[to])
                q.push((PE) {to, dist[to]});
            }
        }
    }
}
int main() {
    scanf("%d%d%d", &n, &m, &starter);
    for (int i = 1, u, v, w; i <= m; i++) {
        scanf("%d%d%d", &u, &v, &w);
        insert(u, v, w);
    }
    dijkstra();
    for (int i = 1; i <= n; i++) {
        printf("%d ", dist[i]);
    }
    return 0;
}

by kiritokazuto @ 2022-11-14 17:03:25

优先队列重载是反着的

struct PE {
    int to, dis;
    bool operator<(const PE &e)const {
        return dis > e.dis;
    }
};

by xingke233 @ 2022-11-14 17:03:41

@clancysam

优先队列写错辣

struct PE {
    int to, dis;
    bool operator<(const PE &e)const {
        return dis > e.dis;
    }
};

by 8atemak1r @ 2022-11-14 17:04:08

@clancysam 优先队列重载运算符写反了


by Dino_chx @ 2022-11-14 20:19:05

谢谢纠错,蒟蒻知道啦。

此贴结


|