# Cod sursa(job #43867)

Utilizator Data 30 martie 2007 16:46:51 Drumuri minime 20 cpp done Arhiva de probleme 1.83 kb
``````#include <cstdio>
#include <cstdlib>
#include <string>
#include <cmath>

#define FIN "dmin.in"
#define FOUT "dmin.out"
#define NMAX 1501
#define INF 0x3f3f3f3f

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

void read ()
{
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);
}
}

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 (d[lv[pmin][i]] - eps > min + cost[pmin][i])
{
d[lv[pmin][i]] = min + cost[pmin][i];
p[lv[pmin][i]] = p[pmin];
}
else
if (d[lv[pmin][i]] + eps > min + cost[pmin][i])
p[lv[pmin][i]] += p[pmin];
}

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

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

read ();
solve ();

return 0;
}

``````