Cod sursa(job #419670)

Utilizator s_holmesSherlock Holmes s_holmes Data 17 martie 2010 20:01:53
Problema Algoritmul lui Dijkstra Scor 0
Compilator cpp Status done
Runda Arhiva educationala Marime 1.63 kb
// catun.cpp : Defines the entry point for the console application.
//

#include <cstdio>
#include <vector>
#include <queue>
#define NMAX 32008
#define INF 1000000001
using namespace std;
int N ,M, K;
vector< pair<int,int> > v[NMAX];
int cost[NMAX];
int cf[NMAX];
int sf[NMAX];
bool F[NMAX];

void citire()
{
	scanf("%d%d%d",&N,&M,&K);
	int x , y , c;
	for(int i = 1 ; i <= K ; i++)
	{
		scanf("%d",&x);
		F[x] = 1;
	}

	for(int i = 1 ; i <= M ; i++)
	{
		scanf("%d %d %d",&x ,&y ,&c);
		v[x].push_back(make_pair(y, c));
		v[y].push_back(make_pair(x, c));
	}
}

struct cmp
{
	bool operator()(const int &a, const int &b)const
	{
		return cost[a] > cost[b];
	}
};

priority_queue<int , vector<int> ,cmp> Q;

void rezolva(int S)
{
	vector<pair<int, int> >::iterator it;
	
	for(int i = 1 ; i <= N ; i++)
		if(i != S)
			cost[i] = INF;
		else
			cost[i] = 0;
	
	Q.push(S);
	while(!Q.empty())
	{
		int min = Q.top();
		Q.pop();
		for(it = v[min].begin() ; it != v[min].end() ; it++)
			if(cost[it->first] > cost[min] + it->second)
			{
				cost[it->first] = cost[min] + it -> second;
				Q.push(it->first);
			}
	}
	
}

void compara(int S)
{
	for(int i = 1 ; i <= N ; i++)
		if(cost[i] < cf[i])
		{
			cf[i] = cost[i];
			sf[i] = S;
		}
}

void scrie()
{
	for(int i = 1 ; i <= N ; i++)
		if(F[i])
			printf("0 ");
		else
			printf("%d ",sf[i]);
}

int main()
{
	freopen("catun.in","r",stdin);
	freopen("catun.out","w",stdout);
	citire();
	memset(cf,INF,NMAX);
	for(int i = 1 ; i <= N ; i++)
		if(F[i])
		{
			rezolva(i);
			compara(i);
		}
	scrie();
	
	return 0;
}