# Cod sursa(job #183921)

Utilizator Data 22 aprilie 2008 18:59:32 Drumuri minime 100 cpp done Arhiva de probleme 1.58 kb
``````#include<cstdio>
#include<vector>
#include<cmath>
#define pb push_back
#define mp std::make_pair<int,double>
std::vector<std::pair<int,double> > a[1501];
int n,m,nr[1501],h[1501],p[1501],i;
double cost[1501],lg;
const double oo=50000.0;
const int mod=104659;
const double precizie=1e-10;
double _abs(double a)
{
if(a<0) return -a;
return a;
}
inline void swap(int x,int y)
{
int aux;
aux=h[y];h[y]=h[x];h[x]=aux;
p[h[x]]=x;p[h[y]]=y;
}
void down(int x)
{
int st,dr;
st=x<<1;dr=st+1;
if(st<=m)
{
if(dr<=m && cost[h[dr]]<cost[h[st]]) st=dr;
if(cost[h[x]]>cost[h[st]])
{
swap(x,st);
down(st);
}
}
}
int get()
{
swap(1,m);
m--;
down(1);
return h[m+1];
}
void up(int x)
{
if(x==1) return;
int t=x>>1;
if(cost[h[t]]>cost[h[x]])
{
swap(x,t);
up(t);
}
}
int main()
{
freopen("dmin.in","r",stdin);
freopen("dmin.out","w",stdout);
scanf("%d %d",&n,&m);
for(int x,y,z,i=1;i<=m;++i)
{
scanf("%d %d %d",&x,&y,&z);
lg=log((double)z);
a[x].pb(mp(y,lg));
a[y].pb(mp(x,lg));
}
cost[1]=(double)0.0;nr[1]=1;h[1]=1;p[1]=1;m=n;
for(i=2;i<=n;i++) cost[i]=oo,h[i]=i,p[i]=i;
int x,y;
double c;
while(1)
{
if(m==0) break;
x=get();
if(cost[x]==oo) break;
for(i=0;i<a[x].size();i++)
{
y=a[x][i].first;
c=a[x][i].second;
if((cost[y]-cost[x]-c)>precizie)
{
cost[y]=cost[x]+c;
nr[y]=nr[x];
up(p[y]);
}
else
if(_abs(cost[y]-cost[x]-c)<=precizie)
nr[y]=(nr[y]+nr[x])%mod;
}
}
for(i=2;i<=n;i++)
printf("%d ",nr[i]);
fclose(stdout);
return 0;
}
``````