Cod sursa(job #556500)

Utilizator cezyGrigore Cezar cezy Data 16 martie 2011 10:18:07
Problema Algoritmul lui Dijkstra Scor 10
Compilator cpp Status done
Runda Arhiva educationala Marime 0.86 kb
#include<fstream>
#include<vector>
#include<queue>
using namespace std;
#define nmax 50100
#define pb push_back
#define inf 1000000000
vector<int> g[nmax],c[nmax];
int d[nmax];
priority_queue <int> q;
int viz[nmax];
int n,sf,inc,m;
void citire()
{
	ifstream fin("dijkstra.in");
	fin>>n>>m;
	int i,a,b,dist;
	for(i=1;i<=m;i++)
		fin>>a>>b>>dist,g[a].pb(b),c[a].pb(dist);
	fin.close();
}
void scrie()
{
	ofstream fout("dijkstra.out");
	int i;
	for(i = 2; i <= n; i++)
        if(d[i]==inf) fout<<0;
		else fout<<d[i]<<' ';
	fout.close();
}
int main ()
{
	citire();
	int i,j,k,a;
    for(i=1;i<=n;i++)
		d[i]=inf;
	d[1]=0;
	q.push(1);
	while(!q.empty())
	{
		k=q.top();
		viz[k]=0;
		q.pop();
		for(i = 0; i < g[k].size(); i++)
        if( d[ g[k][i] ] > d[k] + c[k][i] )
          d[ g[k][i] ] = d[k] + c[k][i], q.push( g[k][i]),sf++;
	}
	scrie();
	return 0;
}