Cod sursa(job #524376)

Utilizator Bogdan_tmmTirca Bogdan Bogdan_tmm Data 21 ianuarie 2011 00:00:39
Problema Algoritmul lui Dijkstra Scor 90
Compilator cpp Status done
Runda Arhiva educationala Marime 1.19 kb
#include<stdio.h>
#include<queue>
#include<vector>
#include<algorithm>
using namespace std;
#define Max 9999999
vector <int> cost(50005,Max);
vector <bool> ut(50005);
class nc
{
public:
	int nod,costInit;
	nc(const int &n,const int &c)
	{
		nod=n;costInit=c;
	}
};
struct cmp
{
	bool operator () (const int &x,const int &y) const
	{
		return cost[x]>cost[y];
	}
};
vector <nc> a[50005];
priority_queue <int,vector <int>,cmp> heap;
int n,m;
void hs()
{
	vector <nc> ::iterator it;
	heap.push(1);cost[1]=0;
	while(!heap.empty())
	{
		int nod=heap.top();heap.pop();
		ut[nod]=false;
		for(it=a[nod].begin();it!=a[nod].end();it++)
		{
			if(cost[it->nod]<=cost[nod]+it->costInit)
				continue;
			cost[it->nod]=cost[nod]+it->costInit;
			if(!ut[it->nod])
			{
				heap.push(it->nod);
				ut[it->nod]=true;
			}
		}
	}
}
int main()
{
	freopen("dijkstra.in","r",stdin);
	freopen("dijkstra.out","w",stdout);
	scanf("%d%d",&n,&m);
	for(int i=0;i<m;i++)
	{
		int x,y,c;
		scanf("%d%d%d",&x,&y,&c);
		a[x].push_back(nc(y,c));
	}
	hs();
	for(int i=2;i<=n;i++)
	{
		if(cost[i]==Max)
		{
			printf("0 ");
			continue;
		}
		printf("%d ",cost[i]);
	}
	return 0;
}