Cod sursa(job #277482)
#include <cstdio>
#include <fstream>
#include <queue>
#define inff 0x3f3f3f
#define MAX_N 50001
using namespace std;
struct nod {int n, cost;};
vector <nod> V[MAX_N];
queue <int> Q;
char viz[MAX_N];
int N,M,D[MAX_N],cati[100];
void citire()
{
int x,y,z;
scanf("%d %d",&N,&M);
for(int i = 1; i <= M; ++i)
{
scanf("%d %d %d",&x,&y,&z);
nod t;
t.n = y;
t.cost = z;
V[x].push_back(t);
}
}
void solve()
{
memset(D, inff, sizeof D);
Q.push(1);
D[1] = 0;
cati[1]=1;
viz[1] ='1';
while(!Q.empty())
{
int nod = Q.front();
Q.pop();
viz[nod]='0';
for(typeof V[nod].begin() p = V[nod].begin(); p < V[nod].end(); p++)
if(D[p->n]>D[nod]+p->cost)
{
cati[p->n]=cati[nod];
D[p->n]=D[nod]+p->cost;
if(viz[p->n]!='1')
{
Q.push(p->n);
viz[p->n]='1';
}
}
else
if (D[p->n]==D[nod]+p->cost)
cati[p->n]+=cati[nod];
}
}
void afisare()
{
for(int i = 2; i <= N; ++i)
printf("%d ",cati[i]);
printf("\n");
}
int main()
{
freopen ("dmin.in","r",stdin);
freopen ("dmin.out","w",stdout);
citire();
solve();
afisare();
return 0;
}