Cod sursa(job #3003697)

Utilizator axel5919Marius Boroica axel5919 Data 15 martie 2023 21:14:35
Problema Distante Scor 0
Compilator cpp-64 Status done
Runda Arhiva de probleme Marime 1.77 kb
#include <bits/stdc++.h>
#include <limits>

using namespace std;
#define NMAX 76005
#define ll long long
ifstream in("catun.in");
ofstream out("catun.out");

struct NOD {
    ll dist, pos, fort;
};

bool operator<(const NOD& a, const NOD& b) {
    return (a.dist > b.dist);
}

int n, m, k;
ll MARE = numeric_limits<ll>::max();
vector<ll> fort;
vector<ll> conn[NMAX], cost[NMAX];
ll dist[NMAX],app[NMAX];
bool selectat[NMAX];
priority_queue<NOD> pq;

/*
    n - asezari
    m - drumuri
    k - fortarete
*/

void solve() {
    for (int i = 1; i <= n; ++i) dist[i] = MARE,app[i]=MARE;
    NOD nod;
    for (auto& n : fort) pq.push({ 0,n,n}), dist[n] = 0, app[n] = -1;

    while (not pq.empty()) {
        nod = pq.top();
        pq.pop();

        ll ndist = nod.dist;
        int pos = nod.pos;

        if ((ndist <= dist[pos]) and (app[pos] != -1)) app[pos] = (nod.fort < app[pos]) ? nod.fort : app[pos];

        if (selectat[pos]) continue;

        selectat[pos]=true;
        for (int i = 0; i < conn[pos].size(); ++i) {
            int vecin = conn[pos][i];
            if (dist[vecin] >= dist[pos] + cost[pos][i]) {
                dist[vecin] = ndist + cost[pos][i], pq.push({ ndist + cost[pos][i],vecin,nod.fort });
            }
        } 
    }
}

int main() {

    in >> n >> m >> k;
    for (int i = 0, ft; i < k; ++i) {
        in >> ft;
        fort.push_back(ft);
    }
    for (int i = 0,a,b,d; i < m; ++i) {
        in >> a >> b >> d;
        conn[a].push_back(b), cost[a].push_back(d);
        conn[b].push_back(a), cost[b].push_back(d);
    }
    solve();
    for (int i = 1; i <= n; ++i) {
        if (app[i] == MARE or app[i] == -1) out << "0 ";
        else out << app[i] << ' ';
    }
    in.close(), out.close();
}