# Cod sursa(job #8529)

Utilizator Data 24 ianuarie 2007 22:24:08 Drumuri minime 25 cpp done Arhiva de probleme 1.98 kb
``````#include <stdio.h>
#include <math.h>
#include <iostream>
#include <vector>

using namespace std;

const double EPS = 1e-5;

vector<int> fii[1501];
vector<double> cost[1501];
int mod[1501];
int nodc;

int heap[1501];
int pozheap[1501];
int lh;
double dist[1501];

int n,m;

void pop( int x );
void push( int x );

double absv( double x )
{
if ( x < 0 ) return ( -1*x );
return x;
}

int main()
{
int a,b;
double c=0;
int i;
freopen("dmin.in","r",stdin);
freopen("dmin.out","w",stdout);

scanf("%d %d\n", &n, &m);

for ( i = 1; i <= m; i++ )
{
scanf("%d %d %lf\n", &a, &b ,&c);
fii[a].push_back( b );
fii[b].push_back( a );
cost[a].push_back( log( c ) );
cost[b].push_back( log( c ) );
}

for ( i = 1; i <= n; i++ )
{
heap[i] = i;
pozheap[ i ] = i;
dist[i] = 10000000;
}
dist[1] = 0;
mod[1] = 1;
lh = n;

while ( lh )
{
nodc = heap[1];
for ( i = 0; i < fii[ nodc ].size(); i++ )
if ( dist[ nodc ] + cost[ nodc ][ i ] - dist[ fii[nodc][i] ] < -1*EPS)
{
dist[ fii[nodc][i] ] = dist[ nodc ] + cost[ nodc ][ i ];
mod[ fii[nodc][i] ] = mod[ nodc ];
pop( pozheap[ fii[nodc][i] ] );
}
else
if ( absv( dist[ nodc ] + cost[ nodc ][ i ] - dist[ fii[nodc][i] ] ) <= EPS )
mod[ fii[nodc][i] ]+=mod[nodc];

heap[1] = heap[lh];
pozheap[ heap[1] ] = 1;
lh--;
push(1);
}

for ( i = 2; i <= n; i++ )
printf("%d ", mod[i] );
printf("\n");

fclose(stdin);
fclose(stdout);

return 0;
}

void pop( int x )
{
int aux;
while ( x > 1 && dist[ heap[x] ] - dist[ heap[x/2] ] < -1*EPS )
{
aux = heap[x];
heap[x] = heap[x/2];
heap[x/2] = aux;

pozheap[ heap[x]   ] = x;
pozheap[ heap[x/2] ] = x/2;

x = x/2;
}
}

void push( int x )
{
int aux,q=0;
while ( q != x )
{
q=x;
if ( q*2 <= lh && dist[ heap[x] ] - dist[ heap[q*2] ] > EPS )
x = q*2;
if ( q*2+1 <= lh && dist[ heap[x] ] - dist[ heap[q*2+1] ] > EPS )
x = q*2+1;

aux = heap[q];
heap[q] = heap[x];
heap[x] = aux;

pozheap[ heap[q] ] = q;
pozheap[ heap[x] ] = x;
}
}
``````