Dijkstra's Algorithm

Lab C++ Advanced 30 points

Read a directed weighted graph and print the shortest distance from node 1 to every node (or INF), using Dijkstra with a min-heap.

Input

n m, then m lines u v w (w ≥ 0).

Output

One line of n distances.

Example

Input

Output

0 3 1 4 7

Sample input available Sample output available

Editor

C++

Hints

Always expand the closest unfinished node; skip stale heap entries.

Solution explanation

With a binary heap, Dijkstra runs in O((n + m) log n).

Show solution

#include <iostream>
#include <queue>
#include <vector>
#include <functional>
using namespace std;

int main() {
    int n, m;
    cin >> n >> m;
    vector<vector<pair<int, long long>>> adj(n + 1);
    for (int i = 0; i < m; i++) {
        int u, v;
        long long w;
        cin >> u >> v >> w;
        adj[u].push_back({v, w});
    }
    const long long INF = -1;
    vector<long long> dist(n + 1, INF);
    priority_queue<pair<long long, int>, vector<pair<long long, int>>, greater<pair<long long, int>>> pq;
    dist[1] = 0;
    pq.push({0, 1});
    while (!pq.empty()) {
        auto [d, u] = pq.top();
        pq.pop();
        if (d != dist[u]) continue;
        for (auto [v, w] : adj[u]) {
            if (dist[v] == INF || d + w < dist[v]) {
                dist[v] = d + w;
                pq.push({dist[v], v});
            }
        }
    }
    for (int i = 1; i <= n; i++) {
        if (dist[i] == INF) cout << "INF";
        else cout << dist[i];
        cout << (i < n ? " " : "\n");
    }
    return 0;
}

Output

Answer