Cod sursa(job #402899)

Utilizator c_e_manuEmanuel Cinca c_e_manu Data 24 februarie 2010 11:49:23
Problema Algoritmul lui Dijkstra Scor 90
Compilator cpp Status done
Runda Arhiva educationala Marime 0.88 kb
#include<fstream>
#include<queue>
#include<vector>
#define MaxN 50005
#define INF 0x3f3f3f3f

using namespace std;

ifstream fin("dijkstra.in");
ofstream fout("dijkstra.out");

vector< pair<int, int> > G[MaxN];
queue<int> qu;
int n,m,a,b,c,d[MaxN],i,X,viz[MaxN];

void bellmanFord()
{	vector< pair <int, int> >::iterator it;
	memset(d, INF, sizeof(d));
	memset(viz, 0, sizeof(viz));
	d[1]=0;
	qu.push(1);
	while(!qu.empty())
	{	X=qu.front();viz[X]=0;
		for(it=G[X].begin();it!=G[X].end();it++)
			if(d[X]+it->second<d[it->first])
			{	d[it->first]=d[X]+it->second;
				if(!viz[it->first])
				{	viz[it->first]=1;
					qu.push(it->first);
				}
			}
		qu.pop();
	}
}

int main()
{	fin>>n>>m;
	for(i=1;i<=m;i++)
	{	fin>>a>>b>>c;
		G[a].push_back(make_pair(b,c));
	}
	bellmanFord();
	for(i=2;i<=n;i++)
		if(d[i]==INF) fout<<"0 ";
		else	fout<<d[i]<<' ';
}