# Cod sursa(job #44095)

Utilizator Data 30 martie 2007 21:09:36 Drumuri minime 100 cpp done Arhiva de probleme 2.06 kb
``````#include <cstdio>
#include <cstdlib>
#include <string>
#include <cmath>

#define FIN "dmin.in"
#define FOUT "dmin.out"
#define NMAX 1501
#define INF 0x3f3f3f3f
#define PRIM 104659
#define eps 1e-10

int *lv[NMAX], gr[NMAX], N, M, s[NMAX], p[NMAX];
double d[NMAX], *cost[NMAX];

{
int x, y, c;

scanf ("%d%d", &N, &M);

for (int i = 1; i <= M; ++ i)
{
scanf ("%d%d%d", &x, &y, &c);
++ gr[x];
++ gr[y];
}

for (int i = 1; i <= N; ++ i)
{
lv[i] = (int *) malloc ((gr[i] + 1) * sizeof (int));
cost[i] = (double *) malloc ((gr[i] + 1) * sizeof (double));
lv[i][0] = 0;
gr[i] = 0;
}

fseek (stdin, 0, SEEK_SET);

scanf ("%d%d", &N, &M);

for (int i = 1; i <= M; ++ i)
{
scanf ("%d%d%d", &x, &y, &c);
lv[x][++lv[x][0]] = y;
lv[y][++lv[y][0]] = x;
cost[x][++gr[x]] = log (c);
cost[y][++gr[y]] = log (c);
}
}

double modulo (double x)
{
if (x >= 0)
return x;
return -x;
}

int equal (double a, double b)
{
if (modulo (a - b) < eps)
return 1;
return 0;
}

void solve ()
{
int pmin;  double min;

for (int i = 1; i <= N; ++ i)
d[i] = 10000000;

d[1] = 0;
p[1] = 1;

for (int k = 1; k <= N; ++ k)
{
min = 10000000;
for (int i = 1; i <= N; ++ i)
if (!s[i])
if (min >= d[i])
{
min = d[i];
pmin = i;
}

s[pmin] = 1;

for (int i = 1; i <= lv[pmin][0]; ++ i)
if (equal (d[lv[pmin][i]] + cost[pmin][i], min))
{
p[pmin] += p[lv[pmin][i]];
if (p[pmin] > PRIM)
p[pmin] -= PRIM;
}

for (int i = 1; i <= lv[pmin][0]; ++ i)
if (d[lv[pmin][i]] - eps > min + cost[pmin][i])
d[lv[pmin][i]] = min + cost[pmin][i];
}

for (int i = 2; i <= N; ++ i)
printf ("%d ", p[i]);
printf ("\n");
}

int
main ()
{
freopen (FIN, "rt", stdin);
freopen (FOUT, "wt", stdout);

solve ();

return 0;
}

``````