Pagini recente » Cod sursa (job #2882965) | Cod sursa (job #1427905) | Cod sursa (job #2333160) | Cod sursa (job #3234719) | Cod sursa (job #3003697)
#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();
}