Pagini recente » Cod sursa (job #1623491) | Cod sursa (job #1824376) | Cod sursa (job #1742221) | Cod sursa (job #2674242) | Cod sursa (job #1206141)
#include <iostream>
#include <fstream>
#include <queue>
#include <algorithm>
using namespace std;
ifstream f("catun.in");
ofstream g("catun.out");
struct muchie
{ int nod,cost; };
struct cmp
{
bool operator() (muchie a,muchie b)
{ return a.cost>b.cost; }
};
priority_queue<muchie,vector<muchie>,cmp> heap;
muchie el,newel;
vector <muchie> v[36005];
int n,m,k,dm[36005],t[36005],use[36005],ant[36005],inf=2147000000;
int main()
{ int i,x,y,z,c,out;
f>>n>>m>>k;
for(i=1;i<=k;i++)
f>>t[i];
for(i=1;i<=k;i++)
{
use[t[i]]=2; ant[t[i]]=t[i];
el.nod=t[i]; el.cost=0;
heap.push(el);
}
for(i=1;i<=n;i++)
if (use[i]) dm[i]=0; else dm[i]=inf;
for(i=1;i<=m;i++)
{
f>>x>>y>>z;
el.nod=y; el.cost=z;
v[x].push_back(el);
el.nod=x;
v[y].push_back(el);
}
while(!heap.empty())
{
el=heap.top(); heap.pop();
x=el.nod;
if (dm[x]==el.cost)
for(i=0;i<v[x].size();i++)
{ y=v[x][i].nod; c=v[x][i].cost;
if (dm[x]+c<dm[y])
{ ant[y]=ant[x];
dm[y]=dm[x]+c;
newel.nod=y;
newel.cost=dm[y];
heap.push(newel);
}
else
{ if (dm[x]+c==dm[y])
ant[y]=min(ant[y],ant[x]);
}
}
}
for(i=1;i<=n;i++)
g<<(use[i]==2?0:ant[i])<<" ";
return 0;
}