Cod sursa(job #279389)
//Bellman - Ford
#include <cstdio>
#include <cmath>
#define epsilon 0.000000001
#define max 1511
#define MIN(a,b) a<b?a:b
#define MAX(a,b) a<b?b:a
using namespace std;
struct muchie{int x,y;
double cost;} a[max];
double d[50001];
int ok,n,m,cati[100000];
int mat[1501][1501];
int main()
{
freopen("dmin.in","r",stdin);
freopen("dmin.out","w",stdout);
scanf("%d %d",&n,&m);
int num=0;
for(int i=1;i<=m;i++)
{
scanf("%d %d %lf",&a[i].x,&a[i].y,&a[i].cost);
a[i].cost=log(a[i].cost);
a[i+m].x=a[i].y;
a[i+m].y=a[i].x;
a[i+m].cost=a[i].cost;
}
for(int i=2;i<=n;i++)
if(d[i]==0)
d[i]=max;
cati[1]=1;
m*=2;
while(ok==0)
{
ok=1;
for(int i=1;i<=m;i++)
if(d[a[i].y]>d[a[i].x]+a[i].cost && fabs(d[a[i].y]-d[a[i].x]-a[i].cost)>epsilon)
{
for (int p=0;p<=n;p++)
{
mat[a[i].y][p]=0;
mat[p][a[i].y]=0;
}
mat[MIN(a[i].y,a[i].x)][MAX(a[i].y,a[i].x)]=1;
d[a[i].y]=d[a[i].x]+a[i].cost;
ok=0;
cati[a[i].y]=cati[a[i].x];
}
else
if (fabs(d[a[i].y]-d[a[i].x]-a[i].cost)<epsilon && mat[a[i].y][a[i].x]==0 && mat[a[i].x][a[i].y]==0)
{
mat[MIN(a[i].y,a[i].x)][MAX(a[i].y,a[i].x)]=1;
cati[a[i].y]+=cati[a[i].x];
ok=0;
}
}
for(int i=2;i<=n;i++)
{
printf("%d ",cati[i]);
}
return 0;
}