Pagini recente » Cod sursa (job #595595) | Cod sursa (job #2161633) | Cod sursa (job #81997) | Cod sursa (job #2272102) | Cod sursa (job #1082645)
#include <iostream>
#include <fstream>
#include <vector>
#include <queue>
using namespace std;
const int inf=1<<30,Nmax=36001;
vector <long long int> v[Nmax];
queue <long long int> q;
long long int cost[Nmax], t[Nmax], n, m, k;
bool fort[Nmax];
void bf()
{
int i,j,a;
while(!q.empty())
{
a=q.front();
for(i=0; i<v[a].size(); i+=2)
{
if(cost[v[a][i]]>=cost[a]+v[a][i+1])
{
if(cost[v[a][i]]==cost[a]+v[a][i+1])
{
if(t[v[a][i]]>t[a])
t[v[a][i]]=t[a];
q.push(v[a][i]);
}
else
{
q.push(v[a][i]);
t[v[a][i]]=t[a];
cost[v[a][i]]=cost[a]+v[a][i+1];
}
}
}
q.pop();
}
}
int main()
{
int x,y,c,i;
ifstream in("catun.in");
in>>n>>m>>k;
for(i=1; i<=n; i++)
{
cost[i]=inf;
}
for(i=0; i<k; i++)
{
in>>c;
q.push(c);
fort[c]=1;
cost[c]=0;
t[c]=c;
}
for(i=0; i<m; i++)
{
in>>x>>y>>c;
v[x].push_back(y);
v[x].push_back(c);
v[y].push_back(x);
v[y].push_back(c);
}
in.close();
bf();
ofstream out("catun.out");
for(i=1; i<=n; i++)
{
if(fort[i]) out<<0<<" ";
else
out<<t[i]<<" ";
}
out.close();
return 0;
}