# Cod sursa(job #174139)

Utilizator Data 8 aprilie 2008 15:14:35 Drumuri minime 0 cpp done Arhiva de probleme 2.12 kb
``````#include <stdio.h>
#include <algorithm>
#define inf 2000000000
#define nMax 50005
#define mMax 250005

using namespace std;

long d[nMax];
long q[nMax];
long poz[nMax];
long n,m,k,i,j,r;
long nod_min,C;
long x[mMax],y[mMax],z[mMax],G[nMax];
long *v[nMax],*c[nMax];
long p[nMax];

void scufunda(long i){
long fiu;
while ((long)(i<<1)<=k){
fiu=i<<1;
if ((long)(fiu|1)<=n)
if (d[q[fiu|1]]<d[q[fiu]])fiu|=1;
if (d[q[fiu]]<d[q[i]]){
swap(q[i],q[fiu]);
poz[q[i]]=i;
poz[q[fiu]]=fiu;
i=fiu;
}
else break;
}
}

void ridica(long i){
long val=q[i];
while (i>1 && d[val]<d[q[i>>1]]){
q[i]=q[i>>1];
poz[q[i]]=i;
i>>=1;
}
q[i]=val;
poz[q[i]]=i;
}

long get_min(){
swap(q[1],q[k]);
poz[q[1]]=1;
poz[q[k]]=k;
k--;
scufunda(1);
return q[k+1];
}

void output(){
for (i=2;i<=n;i++)
printf("%ld ",p[i]);
printf("\n");
}

void dijkstra(){
//initializare
for (i=1;i<=n;i++){
poz[i]=q[i]=i;
d[i]=inf;
}
d[r]=0;
p[r]=1;
k=n;
while (k){
nod_min=get_min();
for (i=1;i<=G[nod_min];i++)
if (d[j=v[nod_min][i]]>d[nod_min]+c[nod_min][i]){
d[j]=d[nod_min]+c[nod_min][i];
p[j]=p[nod_min];
ridica(poz[j]);
}
else if (d[j]==d[nod_min]+c[nod_min][i])p[j]+=p[nod_min];
}
output();
}

int main(){
freopen("dmin.in","r",stdin);
freopen("dmin.out","w",stdout);

scanf("%ld %ld",&n,&m);
r=1;//nod sursa
i=m;
while (m){
scanf("%ld %ld %ld",&x[m],&y[m],&z[m]);
G[x[m]]++;
m--;
}
m=i;
for (i=1;i<=n;i++){
v[i]=new long [G[i]+1];
c[i]=new long [G[i]+1];
G[i]=0;
}
for (i=1;i<=m;i++){
v[x[i]][++G[x[i]]]=y[i];
c[x[i]][G[x[i]]]=z[i];
}

dijkstra();

return 0;
}
``````