Cod sursa(job #768918)

Utilizator dutzulBodnariuc Dan Alexandru dutzul Data 17 iulie 2012 21:34:59
Problema Algoritmul lui Dijkstra Scor 10
Compilator cpp Status done
Runda Arhiva educationala Marime 0.77 kb
#include <fstream>
#include <set>
#include <queue>
#define LE 50600
using namespace std;
ifstream f("dijkstra.in");
ofstream g("dijkstra.out");
vector< pair<int,int> > N[LE];
#define mp make_pair
#define pb push_back
set<pair<int,int> > H;
int dist[LE],nod,i,x,y,cost,m,n,c;

int solve()
{
	H.insert(mp(0,1));
	while (H.size()!=0)
	  {
		nod=(*H.begin()).second;cost=(*H.begin()).first;
		
		H.erase(H.begin());
		
		if (dist[nod]==0)
		{
			dist[nod]=cost;
			
			for(i=0;i<N[nod].size();++i)
			  H.insert(mp(N[nod][i].second+cost,N[nod][i].first));
		}
	}
}
int main()
{
	f>>n>>m;
	for(i=1;i<=n;++i)
	{
		f>>x>>y>>c;
	    N[x].pb(mp(y,c));
	}
	solve();
	
	for(i=2;i<=n;++i) 
		g<<dist[i]<<" ";
	
	
	
f.close();g.close();
return 0;	
}