# Cod sursa(job #43885)

Utilizator Data 30 martie 2007 17:04:04 Drumuri minime 5 cpp done Arhiva de probleme 1.94 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

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

{
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] = (long long *) malloc ((gr[i] + 1) * sizeof (long long));
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]] = c;
cost[y][++gr[y]] = c;
}
}

void solve ()
{
long long pmin, min;

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

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

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

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