链式前向星 指针写法 求调

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

2h_xingren @ 2024-08-19 19:15:26

rt,感觉自己写的很怪,但是能ac,有没有大佬改的更简洁一点

#include <bits/stdc++.h>
#define int long long

using std::cin;
using std::cout;
const int N = 1e5 + 5;
const int M = 2e5 + 5;
int dis[N], cnt, n, m, s;
bool vis[N];
struct edge {
    int v, w;
    edge* next;
    edge* prev;
    edge() {
        next = prev = nullptr;
    }
};
edge* head[N];
void add_edge(int u, int v, int w) {
    if (!head[u]) {
        head[u] = new edge();
        head[u] -> v = v;
        head[u] -> w = w;
    } else {
        head[u] -> prev = new edge();
        head[u] -> prev -> v = v;
        head[u] -> prev -> w = w;
        head[u] -> prev -> next = head[u];
        head[u] = head[u] -> prev;
    }
}

struct node {
    int dis, pos;
    bool operator< (const node& x) const {
        return dis > x.dis;
    }
};
std::priority_queue<node> q;
void dijkstra(int s) {
    memset(dis, 0x3f, sizeof(dis));
    dis[s] = 0;
    q.push({0, s});
    while (!q.empty()) {
        int u = q.top().pos;
        q.pop();
        if (vis[u])
            continue;
        vis[u] = 1;
        for (edge* e = head[u]; e; e = e -> next) {
            int v = e -> v, w = e -> w;
            if (dis[v] > dis[u] + w) {
                dis[v] = dis[u] + w;
                q.push({dis[v], v});
            }
        }
    }
}
signed main(void) {
    cin >> n >> m >> s;
    for (int i = 1; i <= m; i++) {
        int u, v, w;
        cin >> u >> v >> w;
        add_edge(u, v, w);
    }
    dijkstra(s);
    for (int i = 1; i <= n; i++)
        cout << dis[i] << ' ';
    return 0;
}

by Xr0701 @ 2024-08-19 19:26:34

建议换成数组


|