Cod sursa(job #211102)

Utilizator Data 30 septembrie 2008 20:52:56 Drumuri minime 100 cpp done Arhiva de probleme 1.5 kb
``````#include <stdio.h>
#include <vector>
#include <queue>
#include <math.h>
#define nMax 1501
#define inf 1<<30
#define epsilon 0.00000000001
#define pb(a) push_back(a)
using namespace std;
long n,m,i,x,y,z,nod,nod2,nr[nMax];
char iq[nMax];
double c,d[nMax],dif;
vector <int>v[nMax];
vector <double>cost[nMax];

void bellman(){
queue<int>Q;
for (i=2;i<=n;++i)d[i]=inf; d[1]=0; nr[1]=1;
Q.push(1);iq[1]=1;
while (!Q.empty()){
nod=Q.front(); Q.pop(); iq[nod]=0;
int l=v[nod].size();
for (int i=0;i<l;++i){
nod2=v[nod][i];
dif=d[nod]+cost[nod][i]-d[nod2];
if (dif>(-epsilon) && dif<epsilon){
nr[nod2]+=nr[nod];nr[nod2]=(nr[nod2]>104659)?(nr[nod2]-104659):(nr[nod2]);
if (!iq[nod2]){ iq[nod2]=1; Q.push(nod2); }
}
else
if (dif<(-epsilon)){
d[nod2]=d[nod]+cost[nod][i];
nr[nod2]=nr[nod];
if (!iq[nod2]){ iq[nod2]=1; Q.push(nod2); }

}
}
}
}

int main(){
freopen("dmin.in","r",stdin);
freopen("dmin.out","w",stdout);
scanf("%ld %ld",&n,&m);
while (m--){
scanf("%ld %ld %ld",&x,&y,&z);
c=log(z);
v[x].pb(y);v[y].pb(x);
cost[x].pb(c);cost[y].pb(c);
}
bellman();
for (i=2;i<=n;++i)
printf("%ld ",nr[i]);
printf("\n");
return 0;
}
``````