# Cod sursa(job #5317)

Utilizator Data 11 ianuarie 2007 21:00:58 Drumuri minime 10 cpp done Arhiva de probleme 1.56 kb
``````#include<stdio.h>
#define fin "dmin.in"
#define fout "dmin.out"
#define Nmax 1501
#define Mmax 2501
#define Mod 104659
#define Eps 1e-7
int nrsol[Nmax],viz[Nmax],v[Nmax][Mmax],v_cost[Nmax][Nmax];
double cost[Nmax];
int n,m,st[Nmax];
FILE *in,*out;

double absf(double a) {
if (a<0) return -a;
return a;
}

void go() {
int i,nod,poz,x;
double min,a,b;

min=cost[st[1]]; nod=st[1]; poz=1;

for (i=2;i<=st[0];++i) {
a=cost[st[i]];
if(a<min) {
nod=st[i];
poz=i;
min=(double)cost[st[i]];
}
}
/*printf("\n");
for (i=1;i<=n;++i) printf("%lf ",cost[i]);
printf("min: %lf\n\n",min);
*/
st[poz]=st[st[0]];
st[0]--;
viz[nod]=1;

for (i=1;i<=v[nod][0];++i) {
x=v[nod][i]; a=cost[x];
if (!viz[x])
if (a<Eps) {
cost[x]=(double)(cost[nod]*(double)v_cost[nod][i]);
nrsol[x]=nrsol[nod];
st[++st[0]]=x;
}
else {
b=(double)cost[nod]*(double)v_cost[nod][i];
if (absf(a-b)<Eps) {

nrsol[x]=nrsol[x]+nrsol[nod];
if (nrsol[x]>=Mod)
nrsol[x]=Mod-nrsol[x];

}

else

if (absf(a-b)>Eps) {

cost[x]=b;
nrsol[x]=nrsol[nod];
}
}
}

if (st[0]) go();
}

int main() {
int i,j,x,y,c;
in=fopen(fin,"r"); out=fopen(fout,"w");
fscanf(in,"%i%i",&n,&m);

for (i=1;i<=m;++i) {
fscanf(in,"%i%i%i",&x,&y,&c);
v[x][0]++;
v[y][0]++;
v[x][v[x][0]]=y; v_cost[x][v[x][0]]=c;
v[y][v[y][0]]=x; v_cost[y][v[y][0]]=c;
}

cost[1]=1.0; nrsol[1]=1;
st[0]=st[1]=1;

go();

for (i=2;i<=n;++i) {
if (i!=2) fprintf(out," ");
fprintf(out,"%i",nrsol[i]);
}

fprintf(out,"\n");

fclose(in); fclose(out);

return 0;
}
``````