Pagini recente » Cod sursa (job #3031048) | Cod sursa (job #1092814) | Cod sursa (job #503621) | Cod sursa (job #1763127) | Cod sursa (job #419670)
Cod sursa(job #419670)
// catun.cpp : Defines the entry point for the console application.
//
#include <cstdio>
#include <vector>
#include <queue>
#define NMAX 32008
#define INF 1000000001
using namespace std;
int N ,M, K;
vector< pair<int,int> > v[NMAX];
int cost[NMAX];
int cf[NMAX];
int sf[NMAX];
bool F[NMAX];
void citire()
{
scanf("%d%d%d",&N,&M,&K);
int x , y , c;
for(int i = 1 ; i <= K ; i++)
{
scanf("%d",&x);
F[x] = 1;
}
for(int i = 1 ; i <= M ; i++)
{
scanf("%d %d %d",&x ,&y ,&c);
v[x].push_back(make_pair(y, c));
v[y].push_back(make_pair(x, c));
}
}
struct cmp
{
bool operator()(const int &a, const int &b)const
{
return cost[a] > cost[b];
}
};
priority_queue<int , vector<int> ,cmp> Q;
void rezolva(int S)
{
vector<pair<int, int> >::iterator it;
for(int i = 1 ; i <= N ; i++)
if(i != S)
cost[i] = INF;
else
cost[i] = 0;
Q.push(S);
while(!Q.empty())
{
int min = Q.top();
Q.pop();
for(it = v[min].begin() ; it != v[min].end() ; it++)
if(cost[it->first] > cost[min] + it->second)
{
cost[it->first] = cost[min] + it -> second;
Q.push(it->first);
}
}
}
void compara(int S)
{
for(int i = 1 ; i <= N ; i++)
if(cost[i] < cf[i])
{
cf[i] = cost[i];
sf[i] = S;
}
}
void scrie()
{
for(int i = 1 ; i <= N ; i++)
if(F[i])
printf("0 ");
else
printf("%d ",sf[i]);
}
int main()
{
freopen("catun.in","r",stdin);
freopen("catun.out","w",stdout);
citire();
memset(cf,INF,NMAX);
for(int i = 1 ; i <= N ; i++)
if(F[i])
{
rezolva(i);
compara(i);
}
scrie();
return 0;
}