SDA - test 6 - 2019-2020 - Еконт

#include <cmath>
#include <cstdio>
#include <vector>
#include <iostream>
#include <algorithm>
#include <climits>
#include <unordered_map>
#include <queue>

using namespace std;

unordered_map<int, unordered_map<int, int>> graph;
int distances[2 * 100000];

void fillDistances(int start) {
    priority_queue<pair<int, int>, vector<pair<int, int>>, greater<pair<int, int>>> next;

    next.push({ 0, start });

    while (!next.empty()) {
        int currIdx = next.top().second;
        int currDist = next.top().first;
        next.pop();

        if (distances[currIdx] <= currDist)
            continue;

        distances[currIdx] = currDist;

        for (auto neighbour : graph[currIdx]) {
            int nextIdx = neighbour.first;
            int nextDist = neighbour.second + currDist;
            if (distances[nextIdx] <= nextDist)
                continue;
            next.push({ nextDist, nextIdx });
        }
    }
}

int main() {
    int n, m, u, v, w, start;
    cin >> n >> m;

    for (size_t i = 0; i < n; i++)
    {
        distances[i] = INT_MAX;
    }

    for (int i = 0; i < m; i++) {
        cin >> u >> v >> w;
        u--;
        v--;
        if(graph[u][v] == 0 || graph[u][v] > w){
            graph[u][v] = w;
            graph[v][u] = w;
        }
    }

    cin >> start;
    start--;
    fillDistances(start);

    for (int i = 0; i < n; i++) {
        if (i == start)
            continue;
        if (distances[i] == INT_MAX)
            distances[i]  = -1;
        cout << distances[i] << " ";
    }

    return 0;
}