Dijkstra堆优化板子

Dijkstra堆优化板子

2019年11月10日 0 作者 Ender

马上就要比赛了,每天默写一遍基础算法和数据结构保平安

#include <bits/stdc++.h>

const int maxn = 1e5 + 233;
const int maxm = 5e5 + 233;
struct edge {
    int to, dis, next;
} e[maxm];

struct node {
    int dis;
    int pos;
    bool operator<(const node &x) const {
        return x.dis < dis;
    }
};

std::priority_queue<node> q;
int head[maxn], dis[maxn], cnt;
bool vis[maxn];
int n, m, s;

inline void addEdge(int u, int v, int d) {
    cnt++;
    e[cnt].dis = d;
    e[cnt].to = v;
    e[cnt].next = head[u];
    head[u] = cnt;
}

inline void dijkstra() {
    dis[s] = 0;
    q.push((node) {0, s});
    while (!q.empty()) {
        node temp = q.top();
        q.pop();
        int x = temp.pos, d = temp.dis;
        if (vis[x]) continue;
        vis[x] = true;
        for (int i = head[x]; i; i = e[i].next) {
            int y = e[i].to;
            if (dis[y] > dis[x] + e[i].dis) {
                dis[y] = dis[x] + e[i].dis;
                if (!vis[y]) q.push((node) {dis[y], y});
            }
        }
    }
}

int main() {
    std::cin >> n >> m >> s;
    for (int i = 1; i <= n; i++) dis[i] = INT_MAX;
    for (int i = 0; i < m; i++) {
        int u, v, d;
        std::cin >> u >> v >> d;
        addEdge(u, v, d);
    }
    dijkstra();
    for (int i = 1; i <= n; i++) std::cout << dis[i] << " ";
    return 0;
}

clion的代码格式化强无敌不接受反驳