Cod sursa(job #5311)

Utilizator Data 11 ianuarie 2007 19:36:56 Drumuri minime 0 cpp done Arhiva de probleme 1.41 kb
``````#include<stdio.h>
#define fin "dmin.in"
#define fout "dmin.out"
#define Nmax 1501
#define Mmax 2501
#define Mod 104659
#define Inf 2134000000
int cost[Nmax],nrsol[Nmax],v[Nmax][Mmax],v_cost[Nmax][Mmax];
int n,m,st[Nmax];
FILE *in,*out;

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

min=Inf;

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

st[poz]=st[st[0]];
st[0]--;

for (i=1;i<=v[nod][0];++i) {
x=v[nod][i];
if (!cost[x] && x!=1) {
cost[x]=cost[nod]+v_cost[nod][i];
nrsol[x]=nrsol[nod];
st[++st[0]]=x;
}
else
if (cost[x]==(cost[nod]+v_cost[nod][i])) {

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

else
if (cost[x]>(cost[nod]+v_cost[nod][i])) {

cost[x]=cost[nod]+v_cost[nod][i];
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;
}

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