Cod sursa(job #705059)

Utilizator tangredonSilviu Georgescu tangredon Data 3 martie 2012 00:09:16
Problema Algoritmul Bellman-Ford Scor 100
Compilator cpp Status done
Runda Arhiva educationala Marime 1.35 kb
#include <iostream>
#include <fstream>
#include <vector>
#include <set>
#include <queue>
using namespace std;

#define pb push_back
#define mp make_pair
#define OO 99999999

ifstream f ("bellmanford.in");
ofstream g ("bellmanford.out");

vector <int> G[50050],C[50050];
queue <int> Q;
int n,m;
int d[50050];
int cnt[50050];
bool InQ[50050];
bool NG;

void Read();
void Bellman();
void Write();

int main()
{
	Read();
	Bellman();
	Write();
}

void Read ()
{
	f >> n >> m;
	int x ,y,d;
	for ( int i = 1; i <= m ; i++ )
	{
		f >> x >> y >> d;
		G[x].pb(y);
		C[x].pb(d);
	}

}

void Bellman()
{
	for ( int i = 1; i <= n ; i++ )
		d[i] = OO;
	
	d[1] = 0;
	InQ[1] = true;
	Q.push(1);
	NG = false;
	int x,c,nod;
	
	while ( Q.size() > 0 && NG == false )
	{
		x = Q.front();
		Q.pop();
		InQ[x] = false;
		
		for ( unsigned int i = 0 ; i < G[x].size() ; i++ )
			if ( d[x] < OO )
			{
				nod = G[x][i];
				c = C[x][i];
				if ( d[nod] > d[x] + c )
				{
					d[nod] = d[x] + c;
					if ( InQ[nod] == false )
					{
						if ( cnt[nod] > n )
							NG = true;
						else
						{
							Q.push(nod);
							InQ[nod] = true;
							cnt[nod]++;
						}
					}
				}
			}
	}
}

void Write ()
{
	if ( NG )
		g << "Ciclu negativ!\n";
	else
		for ( int i = 2; i <= n ; i++ )
			g << d[i] << ' ';
}