Pagini recente » Cod sursa (job #1301980) | Istoria paginii utilizator/dornescuvlad | Statistici Constantinescu Eiza (elizac2003) | Cod sursa (job #1878238) | Cod sursa (job #3167746)
#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;
}