Dijkstra implementation

For ITK20
mail@pastecode.io avatar
unknown
c_cpp
2 years ago
1.2 kB
19
Indexable
Never
#include <bits/stdc++.h>

#define TASK "bdsp"

#define fst first
#define snd second

using namespace std;

typedef long long int64;
typedef pair<int64, int> ii;

const int64 oo = 1e17;
const int N = 1e5 + 55;

int n, m;

int64 d[N];

vector<ii> ad[N];

void dijkstra() {
    priority_queue<ii, vector<ii>, greater<ii> > pq;
    d[1] = 0;
    for (int u = 2; u <= n; u++)
        d[u] = oo;
    pq.push(ii(0, 1));
    while (pq.size()) {
        int u = pq.top().snd;
        int64 du = pq.top().fst;
        pq.pop();
        if (du != d[u]) continue;
        for (auto& e: ad[u]) {
            int c = e.fst, v = e.snd;
            if (du + c < d[v]) {
                d[v] = du + c;
                pq.push(ii(d[v], v));
            }
        }
    }
}

int main() {
    #ifndef ONLINE_JUDGE
    freopen(TASK".inp", "r", stdin);
    freopen(TASK".out", "w", stdout);
    #endif
    cin.tie(0)->sync_with_stdio(false);
    cin >> n >> m;
    for (int u, v, c; m--;) {
        cin >> u >> v >> c;
        ad[u].push_back(ii(c, v));
    }
    dijkstra();
    for (int u = 1; u <= n; u++)
        cout << d[u] << " ";
    cout << "\n";
}