Cod sursa(job #44091)

Utilizator vlad_popaVlad Popa vlad_popa Data 30 martie 2007 21:08:41
Problema Drumuri minime Scor 25
Compilator cpp Status done
Runda Arhiva de probleme Marime 1.98 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];

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);
   }
}

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]];

     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);

  read ();
  solve ();

  return 0;
}