Cod sursa(job #717574)

Utilizator ILDottoreBogdan Stoian ILDottore Data 20 martie 2012 00:30:14
Problema Algoritmul lui Dijkstra Scor 50
Compilator cpp Status done
Runda Arhiva educationala Marime 1.1 kb
#include<fstream>
#include<queue>
#include<vector>
using namespace std;

#define NMAX 50005
#define inf 99999999
ifstream f("dijkstra.in");
ofstream g("dijkstra.out");

long n,m,s,d[NMAX],viz[NMAX];


struct cmp{
	bool operator () (long x,long y)
	{ return d[x]<d[y]; }
		  };
		  
struct muchie{
	long x;
	long cost;};


vector <muchie> L[NMAX];
priority_queue <long,vector<long>,cmp> q ;





void dijkstra()
{
long nod;	
	
	s=1;d[s]=0;
	for (long i=2;i<=n;i++)
		d[i]=inf;
	q.push(s);
	viz[s]=1;
	
	while(!q.empty())
		{
    nod=q.top();
    q.pop();	
	viz[nod]=0;
	
	for (long i=0;i<L[nod].size();i++)
		if (d[nod]+L[nod][i].cost < d[ L[nod][i].x ] )
		{   d[ L[nod][i].x ] = d[nod]+L[nod][i].cost ;
			
			if (!viz[L[nod][i].x])
			{q.push( L[nod][i].x );
			viz[L[nod][i].x]=1;}
		     }
		}
}

int main()
{
	f>>n>>m;
	
	for (long i=1;i<=m;i++)
	{ long x;
	  muchie y;
	  
	  f>>x>>y.x>>y.cost;
	  
	  L[x].push_back(y);
	}

	
	dijkstra();
	
	for (long i=2;i<=n;i++)
		if (d[i]==inf)
		g<<"0 ";
		else
		g<<d[i]<<" ";

	g<<"\n";	
return 0;}