Cod sursa(job #3167746)

Utilizator andu9andu nita andu9 Data 11 noiembrie 2023 07:16:58
Problema Algoritmul lui Dijkstra Scor 0
Compilator cpp-64 Status done
Runda Arhiva educationala Marime 1.7 kb
#include <fstream>
#include <vector>
#include <utility>
#include <climits>
#include <queue>

std::ifstream fin("catun.in");
std::ofstream fout("catun.out");

const int nMax = 4e4;
const long long INF = LLONG_MAX;

int main () {
    int n, m, k; fin >> n >> m >> k;

    std::vector<int> res(n, nMax);
    std::vector<long long> dist(n, INF);

    std::priority_queue<std::pair<long long, int>> heap;

    for (int i = 0; i < k; i += 1) {
        int x; fin >> x; x -= 1; dist[x] = 0;
        heap.push (std::make_pair (0, x)), res[x] = x;
    }

    std::vector<std::vector<std::pair<int, int>>> graph(
            n, std::vector<std::pair<int, int>> ());

    while (m > 0) {
        int u, v, c; fin >> u >> v >> c; u -= 1, v -= 1;
        graph[u].emplace_back (std::make_pair (v, c));
        graph[v].emplace_back (std::make_pair (u, c));
        m -= 1;
    }


    while (!heap.empty ()) {
        int intermediary = heap.top ().second;
        long long distance = -heap.top ().first;
        heap.pop ();

        if (dist[intermediary] < distance)
            continue;

        for (auto it : graph[intermediary])
            if (dist[it.first] > dist[intermediary] + it.second || (dist[it.first] == dist[intermediary] + it.second && res[it.first] > res[intermediary])) {
                dist[it.first] = dist[intermediary] + it.second;
                heap.push (std::make_pair (-dist[it.first], it.first));
                res[it.first] = res[intermediary];
            }
    }

    for (int i = 0; i < n; i += 1) {
        if (res[i] == i || res[i] == nMax)
            res[i] = -1;
    }

    for (auto x : res)
        fout << x + 1 << ' ';

    return 0;
}