Shortest Routes I

Solution by TioPatinhas — 100 pts

Code / Notes

#include <bits/stdc++.h>
#include <cmath>
using namespace std;

int main() {
    int n, m;
    cin >> n >> m;
    vector<vector<pair<int,int>>> G(n + 1);
    for (int i = 0; i < m; i++) {
        int u, d, v;
        cin >> u >> v >> d;
        G[u].push_back({v, d});
    }

    vector<long long>dist(n + 1, 1e18);

    priority_queue<pair<long long, int>> Q;
    dist[1] = 0;
    Q.push({dist[1], 1});
    while (!Q.empty()) {
        auto [d, v] = Q.top();
        Q.pop();
        d = -d;
        if (d > dist[v]) continue;
        for (auto [u, dvu] : G[v]) {
            if (dist[v] + dvu < dist[u]) {
                dist[u] = dist[v] + dvu;
                Q.push({-dist[u], u});
            }
        } 
    }
    for (int i = 1; i <= n; i++) {
        cout << dist[i] << ' '; 
    }
}

Last updated 4 weeks ago

« Back to problem