Pagini recente » Cod sursa (job #1792999) | Cod sursa (job #1114190) | Cod sursa (job #2676356) | Cod sursa (job #820759) | Cod sursa (job #2100462)
#include <cstdio>
#include <cstring>
#include <vector>
#include <set>
#include <climits>
#define pb push_back
#define mkp make_pair
using namespace std;
const int NNOD=36020;
const int INF=9999999;
vector < pair<int, int> > lst[NNOD];
vector <pair<int, int> >::iterator it;
set < pair<int,int> > snot;
int nnod,nmuc,x,y,cost,ifort,nodcrt,add,veccrt,dnew,nfort;
int inod,lgmuc,imuc;
int vdist[NNOD],zfort[NNOD],vfort[NNOD],aux;
bool viz[NNOD];
int main()
{
freopen ("catun.in","r",stdin);
freopen ("catun.out","w",stdout);
scanf ("%d%d%d",&nnod,&nmuc,&nfort);
for (inod=1; inod<=nnod; ++inod)
{
vdist[inod]=INF;
}
for (ifort=1; ifort<=nfort; ++ifort)
{
scanf("%d",&x);
vdist[x]=0;
vfort[ifort]=x;
zfort[x]=x;
snot.insert(mkp(0,x));
}
for (imuc=1; imuc<=nmuc; ++imuc)
{
scanf ("%d%d%d",&x,&y,&cost);
lst[x].pb(mkp(cost,y));
lst[y].pb(mkp(cost,x));
}
while (!snot.empty())
{
nodcrt=snot.begin()->second;
snot.erase(snot.begin());
//if (viz[nodcrt]) continue;
// viz[nodcrt]=1;
for (it=lst[nodcrt].begin(); it!=lst[nodcrt].end(); ++it)
{
lgmuc=it->first;
veccrt=it->second;
dnew=vdist[nodcrt]+lgmuc;
if (dnew<vdist[veccrt])
{
if (vdist[veccrt]!=INF)
{
snot.erase(snot.find(mkp(vdist[veccrt],veccrt)));
}
zfort[veccrt]=zfort[nodcrt];
vdist[veccrt]=dnew;
snot.insert(mkp(dnew,veccrt));
}
if (vdist[veccrt]==dnew)
{
aux=zfort[veccrt];
zfort[veccrt]=min(aux,zfort[nodcrt]);
}
}
}
for (ifort=1; ifort<=nfort; ++ifort)
{
zfort[vfort[ifort]]=0;
}
for (inod=1; inod<=nnod; ++inod)
{
printf("%d ",zfort[inod]);
}
return 0;
}