Cod sursa(job #669396)

Utilizator lucian666Vasilut Lucian lucian666 Data 26 ianuarie 2012 21:08:59
Problema Ubuntzei Scor 5
Compilator cpp Status done
Runda Arhiva de probleme Marime 1.17 kb
#include<fstream>
#define INF 99999999
using namespace std;
ofstream out("ubuntzei.out");
int a[2001][2001],uz[2001],d[2001],T[2001],n,m,k,oras[2001],drumm[2001];
void citire();
void drum(int x);
int dijkstra(int start);
int main()
{
	citire();
	dijkstra(1);
	drum(4);
	return 0;
}
void citire()
{
	ifstream in("ubuntzei.in");
	in>>n>>m;
	in>>k;
	for(int jj=1;jj<=k;jj++)
		in>>oras[jj];
	int x,y,c;
	for(;m;m--)
	{
		in>>x>>y>>c;
		a[x][y]=a[y][x]=c;
	}
	for(int i=1;i<=n;i++)
		for(int j=1;j<=n;j++)
			if(a[i][j]==0&&i!=j)
				a[i][j]=a[j][i]=INF;
}

void drum(int x)
{
	int i,mm;
	mm=0;
	while(T[x])
	{
		drumm[++mm]=x;
		x=T[x];
	}
	drumm[++mm]=x;
	out<<mm+1<<" ";
	out<<'\n';
}
int dijkstra(int start)
{
	int i,j,k,poz;
	for(int i=1;i<=n;i++)
	{
		d[i]=a[start][i];
		uz[i]=0;
		T[i]=start;
	}
	uz[start]=1;
	T[start]=0;
	for(i=1;i<n;i++)
	{
		int minim=INF;
			for(j=1;j<=n;j++)
				if(uz[j]==0&&d[j]<minim)
				{
					minim=d[j];
					poz=j;
				}
				uz[poz]=1;
					for(k=1;k<=n;k++)
						if(d[k]>d[poz]+a[poz][k]&&uz[k]==0)
						{
							d[k]=d[poz]+a[poz][k];
							T[k]=poz;
						}
	}
	return 1;
}