Pagini recente » Cod sursa (job #2490513) | Cod sursa (job #2714564) | Cod sursa (job #954673) | Cod sursa (job #1242439) | Cod sursa (job #2422553)
#include <iostream>
#include <fstream>
#include <bitset>
#include <limits.h>
#include <vector>
#include <queue>
#include <algorithm>
#define pb push_back
#define LMAX 36125
using namespace std;
typedef pair<int, int> PII;
int N, M, K, is_catun[LMAX], f[LMAX], D[LMAX];
vector <PII> E[LMAX];
priority_queue<PII, vector<PII>, greater<PII>> Q;
void Dijkstra()
{
while(!Q.empty())
{
int len = Q.top().first, nod = Q.top().second;
Q.pop();
if(len != D[nod])
continue;
for(auto it : E[nod])
if(len + it.second < D[it.first])
{
D[it.first] = len + it.second;
f[it.first] = f[nod];
Q.push({D[it.first], it.first});
}
else if(len + it.second == D[it.first])
f[it.first] = min(f[it.first], f[nod]);
}
}
void init()
{
for(int i = 1; i<=N; i++)
D[i] = INT_MAX;
}
int main()
{
ifstream fin("catun.in");
ofstream fout("catun.out");
fin >> N >> M >> K;
init();
for(int i = 1 ;i<=K; i++)
{
int numar;
fin >> numar;
is_catun[numar] = 1;
D[numar] = 0;
f[numar] = numar;
Q.push({0,numar});
}
for(int i = 1; i<=M; i++)
{
int x, y, z;
fin >> x >> y >> z;
E[x].pb({y, z});
E[y].pb({x, z});
}
Dijkstra();
for(int i = 1; i<=N; i++)
if(is_catun[i])
fout << "0 ";
else
fout << f[i] <<' ';
}