Pagini recente » Cod sursa (job #960785) | Cod sursa (job #673501) | Cod sursa (job #3135037) | Cod sursa (job #263596) | Cod sursa (job #3260209)
#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] << " ";
}
}