Cod sursa(job #534372)

Utilizator radubbRadu B radubb Data 15 februarie 2011 17:03:48
Problema Algoritmul lui Dijkstra Scor 100
Compilator cpp Status done
Runda Arhiva educationala Marime 0.85 kb
#include <fstream>
#include <vector>
#include <queue>
using namespace std;

#define nmax 50001
long n, m;
vector < pair<long, long> > v[nmax];
queue <long> Q;
long d[nmax];

inline void citire()
{
	long x, y, c;
	ifstream in("dijkstra.in"); in>>n>>m;
	for(long i=1; i<=m; i++)
	{
		in>>x>>y>>c;
		v[x].push_back( make_pair(y, c) );
	}
}

inline void afisare()
{
	ofstream out("dijkstra.out"); 
	for(long i=2; i<=n; i++)
		out<<d[i]<<" ";
}

void bellman_ford()
{
	long nod, next;
	Q.push(1);
	while(!Q.empty())
	{
		nod = Q.front(); Q.pop();
		for(long i=0; i<v[nod].size(); i++)
			if(d[nod]+v[nod][i].second < d[ v[nod][i].first ] || d[v[nod][i].first]==0 )
			{
				d[ v[nod][i].first ] = d[nod] + v[nod][i].second;
				Q.push(v[nod][i].first);
			}
	}
}

int main()
{
	citire();
	bellman_ford();
	afisare();
	return 0;
}