Cod sursa(job #257719)

Utilizator lucian_chisLucian Chis lucian_chis Data 13 februarie 2009 21:07:01
Problema Algoritmul lui Dijkstra Scor 0
Compilator cpp Status done
Runda Arhiva educationala Marime 1 kb
#include<stdio.h>
#include<values.h>
#include<fstream.h>

long a[10000][10000],n,m,d[10000],s[10000];

void init ()
	{
	long i,j;
	for (i=1;i<=n;++i)
		{
		d[i]=MAXLONG;
		for (j=1;j<=n;++j)
			a[i][j]=MAXLONG;
		}
	}

void read ()
	{
	ifstream f("dijkstra.in");
	f>>n>>m;
	init ();
	long i,x,y,c;
	for (i=1;i<=m;++i)
		{
		f>>x>>y>>c;
		a[x][y]=c;
		}
	f.close();
	}

void solve ()
	{
	long i,j,min,poz;
	s[1]=1;
	d[1]=0;
	for (i=1;i<=n;++i)
		if (a[1][i]<MAXLONG)
			{
			d[i]=a[1][i];
			//t[i]=1;
			}
	for (i=1;i<=n-1;++i)
		{
		min=MAXLONG;
		for (j=1;j<=n;++j)
			if (d[j]<min && !s[j])
				{
				min=d[j];
				poz=j;
				}
		s[poz]=1;
		for (j=1;j<=n;++j)
			if (!s[j] && a[poz][j]!=MAXLONG && d[j]>d[poz]+a[poz][j])
				{
				d[j]=d[poz]+a[poz][j];
				//t[j]=poz;
				}
		}
	}

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

int main ()
{
read ();
solve ();
write ();
return 0;
}