# Cod sursa(job #5999)

Utilizator Data 16 ianuarie 2007 18:08:45 Drumuri minime 0 cpp done Arhiva de probleme 2.73 kb
``````#include<stdio.h>
#include<vector>
#include<math.h>

const int maxn = 10000;
const int inf = 10000000;

using namespace std;

vector <int>  vect[maxn];
vector <double>  vect2[maxn];
int c;
int h[maxn];
double cost[maxn];
int n;
int m;
int i;
int x,y;
int poz[maxn];
int l;
int nrp[maxn];

int cmpf(int i,int j)
{
return cost[h[i]]>cost[h[j]];
}

int swap(int i,int j)
{
int aux=h[i];
h[i]=h[j];
h[j]=aux;
aux=poz[h[i]];
poz[h[i]]=poz[h[j]];
poz[h[j]]=aux;
}

void push(int i)
{
while((cmpf(i,i*2)&&i*2<=l)||(cmpf(i,i*2+1)&&i*2+1<=l))
{
if (i*2+1>l||cmpf(i*2+1,i*2))
{
swap(i,i*2);
i*=2;
}
else
{
swap(i,i*2+1);
i=i*2+1;
}
}

}

void pop(int i)
{
while(cmpf(i/2,i)&&i>1)
{
swap(i/2,i);
i/=2;
}
}

int rem()
{
int aux=h[1];
h[1]=h[l];
h[l]=0;
poz[h[1]]=1;
poz[h[l]]=0;
l--;
push(1);
return aux;
}

{
l++;
h[l]=i;
poz[i]=l;
pop(i);
}

int main()
{
freopen("dmin.in","r",stdin);
freopen("dmin.out","w",stdout);
scanf("%d %d",&n,&m);
for(i=1;i<=m;i++)
{
scanf("%d %d %d",&x,&y,&c);
vect[x].push_back(y);
vect[y].push_back(x);
vect2[x].push_back(log(c));
vect2[y].push_back(log(c));

}
for(i=2;i<=n;i++)
{
cost[i]=inf;

}
nrp[1]=1;
for(i=1;i<=n;i++)
{
}
while(l)
{
x=rem();
vector <int>:: iterator it;
vector <double>:: iterator it1;
for(it=vect[x].begin(), it1=vect2[x].begin();it!=vect[x].end();it++,it1++)
{
if (cost[x]+(*it1)==cost[*it])
{
nrp[*it]=(nrp[*it]+nrp[x])%104659;
}

if (cost[x]+(*it1)<cost[*it])
{
cost[*it]=cost[x]+(*it1);
nrp[*it]=nrp[x];
pop(poz[*it]);
}
}
}
for(i=2;i<=n;i++)
{
printf("%d ",nrp[i]);
}
return 0;
}

``````