Challenge: Shortest Distances

Lab C++ Intermediate 20 points

Read a graph with one-way roads that have lengths, and a start. Print the shortest distance from the start to every place 0 … n − 1, or -1 if unreachable. Use Dijkstra.

Input

Line 1: n m. Then m lines a b w (road a → b, length w ≥ 0). Last line: the start.

Output

n numbers separated by spaces.

Example

Input

Output

0 3 1 4

Sample input available Sample output available

Editor

C++

Hints

dist = LLONG_MAX except the start.

Skip popped entries that are out of date.

Relax: if d + w < dist[b], update and push.

Solution explanation

Once a place is popped with its true distance, it never improves again.

Show solution

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

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

Output

Answer