# Cod sursa(job #43094)

Utilizator Data 29 martie 2007 20:14:51 Drumuri minime 0 cpp done Arhiva de probleme 2.17 kb
``````#include <math.h>
#include <iomanip.h>
#include <fstream.h>
#define mx 1502
#define bz 104659
#define aprox 0.0001
ifstream fi("dmin.in");
ofstream fo("dmin.out");

struct muchie
{int y;
double ct;
muchie *next;};

int m,n;
muchie *v[mx];

double cmin[mx];
long nrd[mx];

int use[mx];
int dru[mx];

int ord[mx];
int od;

double abs(double k)
{if (k<0) return -k;
return k;}

{muchie *p;
p=new muchie;
p->y=b;
p->ct=c;
p->next=k;
k=p;}

void citire()
{int i;
int a,b;
double c,r;
fi>>n>>m;
for (i=0;i<m;i++)
{fi>>a>>b>>c;
r=log10(c);
fi.close();}

void nullif(muchie *&k)
{muchie *p;
while (k!=NULL)
{p=k;
k=k->next;
delete p;}}

void sortod(int l,int r)
{int i=l;
int j=r;
int aux;
double w=cmin[ord[(l+r)/2]];
do{while (cmin[ord[i]]<w && (w-cmin[ord[i]]>aprox)) i++;
while (cmin[ord[j]]>w && (cmin[ord[j]]-w>aprox)) j--;
if (i<=j) {aux=ord[i];
ord[i]=j;
ord[j]=aux;
i++;j--;}}
while (i<=j);
if (l<j) sortod(l,j);
if (i<r) sortod(i,r);}

int pas()
{int i,j;
int r=0;
int a,b;
double c,w;
muchie *p;
od=0;
for (i=2;i<=n;i++)
if (use[i]==0 && dru[i]==1)
{ord[od]=i;
use[i]=1;
r=1;
od++;}
sortod(0,od-1);
for (i=0;i<od;i++)
{a=ord[i];
for (p=v[a];p!=NULL;p=p->next)
{b=p->y;
c=p->ct;
dru[b]=1;
w=cmin[a]+c;
if (w<cmin[b] && (cmin[b]-w>aprox))
{cmin[b]=w;
nrd[b]=nrd[a];}
else if (abs(cmin[b]-w)<aprox)
{nrd[b]+=nrd[a];
nrd[b]%=bz;}}}
return r;}

int main()
{int i,r;
muchie *p;
citire();
for (i=2;i<=n;i++)
{use[i]=0;
dru[i]=0;
cmin[i]=2000000000;}
for (p=v[1];p!=NULL;p=p->next)
{dru[p->y]=1;
cmin[p->y]=p->ct;
nrd[p->y]=1;}
do{r=0;
r=pas();}
while (r==1);
for (i=2;i<n;i++)
fo<<nrd[i]<<' ';
fo<<nrd[n]<<'\n';
for (i=1;i<=n;i++)
nullif(v[i]);
fo.close();
return 0;}``````