# Cod sursa(job #6310)

Utilizator Data 18 ianuarie 2007 20:08:23 Drumuri minime 5 cpp done Arhiva de probleme 2.24 kb
``````#include <iostream>
#include <stdio.h>
#include <vector>
#include <math.h>

#define EPS 1e-10
using namespace std;

const double INF = 1000000.0;

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

int n,m,lh;

double distmin[1501];
int mod[1501];
int heap[1501];
int pozheap[1501];

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

int main()
{
int i,j;
int nodc;
int a,b,c;
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 %d\n", &a, &b, &c);
fii[a].push_back(b);
fii[b].push_back(a);
cost[a].push_back( log( (double) c) );
cost[b].push_back( log( (double) c) );
if ( i <= n )
{
heap[ i ] = i;
pozheap[ i ] = i;
distmin[ i ] = INF;
}
}

distmin[ 1 ] = 0.0;
mod[ 1 ] = 1;
lh = n;

while ( lh )
{
nodc = heap[ 1 ];

for ( i = 0; i < fii[ nodc ].size(); i++ )
if ( distmin[ fii[nodc][i] ] - ( distmin[ nodc ] + cost[nodc][i] ) > EPS   )
{
distmin[ fii[nodc][i] ] = distmin[nodc] + cost[nodc][i];
mod[ fii[ nodc ][ i ] ] = mod[ nodc ];
pop( pozheap[ fii[ nodc ][ i ] ] );
}
else
if ( fabs( distmin[ fii[nodc][i] ] - ( distmin[ nodc ] + cost[ nodc ][ i ] ) ) <= EPS)
{
mod[ fii[ nodc ][ i ] ] += mod[ nodc ];
mod[ fii[ nodc ][ i ] ] %= 104659;
}
heap[1] = heap[lh];
pozheap[ heap[1] ] = 1;
lh--;

push(1);
}

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

fclose(stdin);
fclose(stdout);

return 0;
}

void pop( int x )
{
int aux;
while ( x > 0 &&  distmin[ heap[x] ] - distmin[ heap[x/2] ] < 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 q=0,aux;
while ( q!=x )
{
q=x;

if ( 2*q <= lh && distmin[ heap[x] ] - distmin[ heap[2*q] ] > EPS)
x = 2*q;
if ( 2*q+1 <= lh && distmin[ heap[x] ] - distmin[ heap[2*q+1] ] >EPS )
x = 2*q+1;

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

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

x=q;
}
}

``````