# Cod sursa(job #4811)

Utilizator Data 7 ianuarie 2007 19:54:34 Drumuri minime 0 cpp done Arhiva de probleme 1.65 kb
``````#include <stdio.h>
#include <math.h>

#define NMAX 1501
#define MMAX 2501
#define INFY 999999999.0
#define ALAS 104659
#define eps 1e-10
#define abs(a) ((a<0)?(-a):(a))

long i,j,n,m,LUAT[NMAX],A[NMAX][NMAX],D[NMAX];
double C[NMAX];

int main(void)
{
// Citesc Datele
freopen("dmin.in","r",stdin);
freopen("dmin.out","w",stdout);

scanf("%ld%ld",&n,&m);
for (i=1;i<=m;i++)
{
long x,y,z;
scanf("%ld%ld%d",&x,&y,&z);
A[x][y]=z;
A[y][x]=z;
}

// Fac toate costurile pe drumuri infinit mai putin cel de pe 1 care e 1
for (i=1;i<=n;i++)
C[i]=0;
for (i=1;i<=n;i++)
C[i]=INFY;
C[1]=1; LUAT[1]=0; D[1]=1;

// Dijsktra
long DEX=0;
for (DEX=1;DEX<=n;DEX++)
{
double MAX=INFY;
long NOD_MAX;

// Caut nodul in care se ajunge cu drum minim
for (i=1;i<=n;i++)
if (C[i] < MAX && !LUAT[i])
{
MAX=C[i];
NOD_MAX=i;
}

// Marchez nodul curent ca fiind luat
LUAT[NOD_MAX] = 1;

// Ma duc pe toti fii acestui nod si incerc sa expandez drumul
for (i=1;i<=n;i++)
if (A[NOD_MAX][i])
{
if (abs(C[i] - (C[NOD_MAX] + (double)A[NOD_MAX][i])) > eps)
{
C[i] =C[NOD_MAX] + (double)A[NOD_MAX][i];
D[i] = D[NOD_MAX] % ALAS;
}
else
if (abs((C[NOD_MAX] + (double)A[NOD_MAX][i]) - C[i]) <= eps)
{
D[i]+=D[NOD_MAX];
D[i]=D[i] % ALAS;
}
}
}

for (i=2;i<=n;i++)
printf("%ld ",D[i]);

return 0;
}
``````