Pagini recente » Sandbox (cutiuţa cu năsip) | Cod sursa (job #2624606) | Cod sursa (job #1450461) | Cod sursa (job #1832234) | Cod sursa (job #577013)
Cod sursa(job #577013)
#include <fstream>
#include <vector>
using namespace std;
const int N=100001,inf=1<<30;
vector<int> a[N],cost[N];
int v[3*N],mark[N],fort[N],n,m,k;
long long dist[N];
bool use[N];
ifstream in("catun.in");
ofstream out("catun.out");
inline void sch(int &a,int &b)
{
int c=a;a=b;b=c;
}
inline bool cmp(int a,int b)
{
return dist[a]<dist[b] || dist[a]==dist[b] && a<b;
}
inline void up(int x)
{
if (x>1 && cmp(v[x],v[x>>1]))
{
sch(v[x],v[x>>1]);
up(x>>1);
}
}
inline void down(int x)
{
int m=x,s=x<<1,d=s+1;
if (s<=v[0] && cmp(v[s],v[m]))
m=s;
if (d<=v[0] && cmp(v[d],v[m]))
m=d;
if (m!=x)
{
sch(v[m],v[x]);
down(m);
}
}
inline void push(int x)
{
v[++v[0]]=x;
up(v[0]);
}
inline void pop(int &x)
{
x=v[1];
v[1]=v[v[0]--];
down(1);
}
void dijkstra()
{
int x,y,c;
while (v[0])
{
pop(x);
if (use[x])
continue;
use[x]=true;
for (unsigned int i=0;i<a[x].size();i++)
{
y=a[x][i];c=cost[x][i];
if (dist[y]>dist[x]+c || dist[y]==dist[x]+c && mark[y]>=mark[x])
{
dist[y]=dist[x]+c;
mark[y]=mark[x];
push(y);
}
}
}
}
int main()
{
int x,y,c,i;
in>>n>>m>>k;
for (i=1;i<=k;i++)
in>>fort[i];
while (m--)
{
in>>x>>y>>c;
a[x].push_back(y);
a[y].push_back(x);
cost[x].push_back(c);
cost[y].push_back(c);
}
for (i=1;i<=n;i++)
dist[i]=inf;
for (i=1;i<=k;i++)
{
x=fort[i];
dist[x]=0;
mark[x]=x;
push(x);
}
dijkstra();
for (i=1;i<=k;i++)
mark[fort[i]]=0;
for (i=1;i<=n;i++)
out<<mark[i]<<" ";
out<<"\n";
return 0;
}