Cod sursa(job #1071261)

Utilizator ionut_ungureanuUngureanu Vladut Ionut ionut_ungureanu Data 2 ianuarie 2014 20:30:17
Problema Algoritmul lui Dijkstra Scor 100
Compilator cpp Status done
Runda Arhiva educationala Marime 1.13 kb
#include <cstdio>
#include <vector>
#include <queue>
#define NMAX 50001
#define INF 1000000000
#define FIN "dijkstra.in","r",stdin
#define FOUT "dijkstra.out","w",stdout

using namespace std;

int n, m,x,y,c,i,vfmin;

vector <pair<int, int> >G[NMAX];
vector <pair<int, int> >::iterator it;
vector <int>dmin(NMAX,INF);

class cmp
{
public:
	bool operator () (const int& x, const int& y)
	{
		return dmin[x] > dmin[y];
	}
};

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


void dijkstra()
{

	dmin[1] = 0;
	H.push(1);

	while (!H.empty())
	{
		vfmin = H.top();
		H.pop();

		for (it = G[vfmin].begin(); it != G[vfmin].end();++it)
			if (dmin[(*it).first] > dmin[vfmin] + (*it).second)
			{
				dmin[(*it).first] = dmin[vfmin] + (*it).second;
				H.push( (*it).first );
			}
	}
}

int main()
{

	freopen(FIN);
	freopen(FOUT);

	scanf("%d %d",&n,&m);

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


	dijkstra();

	for (i = 2; i <= n; i++)
        if(dmin[i]!=INF)
            printf("%d ",dmin[i]);
    else printf("0 ");

	return 0;
}