# Cod sursa(job #50618)

Utilizator Data 7 aprilie 2007 23:01:48 Drumuri minime 20 cpp done Arhiva de probleme 2.76 kb
``````#include <cstdio>
#include <cmath>
#include <cstdlib>
#include <vector>
#include <queue>
#define pb push_back
#define maxn 1505
#define eps (1e-10)
#include <string>
#define mod 104659
using namespace std;

struct nod { double c; int x; nod(){}; nod(int a, double b){ x=a; c=b;};};

vector<vector<nod> >a;
int n, m;
double d[maxn];
int sol[maxn];

void citire()
{
int p, q,c;double C;
freopen("dmin.in", "r", stdin);
scanf("%d %d\n", &n, &m);
a.resize(n+1);
for(int i=1;i<=m;i++)
{
scanf("%d %d %d\n", &p, &q, &c);
C=(double) log(c);
a[p].pb(nod(q, C));
a[q].pb(nod(p, C));
}
}
bool operator<(const nod &a, const nod & b)
{
if(b.c-a.c>eps) return 1;
return 0;
}
void dijkstra()
{
int i, j, nh=n, u;
bool viz[maxn];
priority_queue<nod> Q;
vector<nod> ::iterator it;
Q.push(nod(1, 0));
for(i=1;i<=n;i++) d[i]=1000000000;
memset(viz, 0,sizeof(viz));
d[1]=0;
sol[1]=1;
while(!Q.empty() && nh)
{
u=Q.top().x;
Q.pop();
if(viz[u]) continue;
viz[u]=1;
--nh;
for(it=a[u].begin();it!=a[u].end();++it)
if((d[it->x] - (d[u]+it->c)) >eps)
{
d[it->x]=d[u]+it->c;
Q.push(nod(it->x, d[it->x]));
//sol[it->x]=sol[u];
//	sol[it->x]%=mod;
}
/*
else
if(fabs((d[it->x] - (d[u]+it->c))) <=eps )
{
sol[it->x]+=sol[u];
sol[it->x]%=mod;
}
*/

/*
for(it=a[u].begin();it!=a[u].end();++it)
if((d[it->x] - (d[u]+it->c)) <=eps && it->x !=u && !viz[it->x])
{
sol[it->x]+=sol[u];
sol[it->x]%=mod;
*/

}
//	for(i=1;i<=n;i++) printf("%d ", sol[i]);

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

int memo(int nd)
{
//printf("%d\n", nd);

if(nd==1) return 1;
if(sol[nd]) return sol[nd];

for(vector<nod>::iterator it=a[nd].begin();it!=a[nd].end();++it)
if(fabs((d[nd] -(d[it->x]+it->c))) <=eps )
{
//	printf("%lf %lf %lf\n", d[nd], d[it->x]+it->c,(d[nd] -(d[it->x]+it->c)));
sol[nd]+=memo(it->x), sol[nd]%=mod;
}
return sol[nd];
}

void solve()
{
int Q[maxn], p=1, q=1, viz[maxn];
memset(Q, 0, sizeof(Q));
memset(viz, 0, sizeof(viz));
Q[1]=1;
sol[1]=1;
viz[1]=1;
int u, i;
vector<nod>::iterator it, jt;

while(p<=q)
{
u=Q[p++];

for(it=a[u].begin();it!=a[u].end();++it)
if(!viz[it->x])
{
viz[it->x]=1;
i=it->x;
for(jt=a[i].begin();jt!=a[i].end();++jt)
if(viz[jt->x] && ((d[jt->x] - (d[i]+jt->c)) <=eps))
{
sol[it->x]+=sol[jt->x];
sol[it->x]%=mod;
}
}
}
//	for(i=1;i<=n;i++) printf("%d ", sol[i]);
}
int main()
{
citire();
dijkstra();

for(int i=n;i>1;i--) memo(i);
//memo(n);
freopen("dmin.out", "w", stdout);
for(int i=2;i<=n;i++) printf("%d ", sol[i]);
//solve();
return 0;
}

``````