Cod sursa(job #3260209)

Utilizator Barbu_MateiBarbu Matei Barbu_Matei Data 30 noiembrie 2024 18:18:12
Problema Drumuri minime Scor 0
Compilator cpp-64 Status done
Runda Arhiva de probleme Marime 1.8 kb
#include <bits/stdc++.h>
using namespace std;

int n, m, k;
vector<pair<int, int>> v[36001];
int len[36001], fort[36001], ans[36001];

struct elem {
    int len, node;
};

class comp {
public:
    bool operator()(elem a, elem b) {
        return a.len > b.len;
    }
};

void dijkstra() {
    memset(len, 0x3f, sizeof(len));
    memset(ans, 0x3f, sizeof(ans));
    priority_queue<elem, vector<elem>, comp> q;
    for (int i = 1; i <= k; ++i) {
        q.push({0, fort[i]});
        len[fort[i]] = 0;
        ans[fort[i]] = fort[i];
    }
    while (!q.empty()) {
        int node = q.top().node;
        int qlen = q.top().len;
        q.pop();
        if (qlen != len[node]) {
            continue;
        }
        for (int i = 0; i < v[node].size(); ++i) {
            if (len[node] + v[node][i].second < len[v[node][i].first]) {
                len[v[node][i].first] = len[node] + v[node][i].second;
                ans[v[node][i].first] = ans[node];
                q.push({len[v[node][i].first], v[node][i].first});
            } else if (len[node] + v[node][i].second == len[v[node][i].first] && ans[node] < ans[v[node][i].first]) {
                ans[v[node][i].first] = ans[node];
            }
        }
    }
}

int main() {
    ifstream cin("catun.in");
    ofstream cout("catun.out");
    cin >> n >> m >> k;
    for (int i = 1; i <= k; ++i) {
        cin >> fort[i];
    }
    for (int i = 1; i <= m; ++i) {
        int x, y, z;
        cin >> x >> y >> z;
        v[x].push_back({y, z});
        v[y].push_back({x, z});
    }
    dijkstra();
    for (int i = 1; i <= k; ++i) {
        ans[fort[i]] = 0;
    }
    for (int i = 1; i <= n; ++i) {
        if (ans[i] == 0x3f3f3f3f) {
            ans[i] = 0;
        }
        cout << ans[i] << " ";
    }
}