Cod sursa(job #577013)

Utilizator mihai995mihai995 mihai995 Data 9 aprilie 2011 17:54:35
Problema Algoritmul lui Dijkstra Scor 0
Compilator cpp Status done
Runda Arhiva educationala Marime 1.59 kb
#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;
}