# Cod sursa(job #2408471)

Utilizator Data 17 aprilie 2019 23:40:52 Drumuri minime 100 cpp-64 done Arhiva de probleme 1.88 kb
``````#include <bits/stdc++.h>
#define MOD 104659
#define pb push_back
#define mp make_pair
#define f first
#define s second
using namespace std ;
const int NR = 1505 ;
const long double oo = 100000 ;
const double ER = 0.000000001;
ifstream in ("dmin.in") ;
ofstream out ("dmin.out") ;
vector < pair < int , long double > > v [ NR ] ;
vector < int > way ( NR , 0 ) ;
vector < long double > d ( NR , oo ) ;
int n , m ;
struct cmp {
inline bool operator() ( const pair < int , long double > i , const pair < int , long double > j )  {
return i.s > j.s ;
}
};
priority_queue < pair < int , long double > , vector < pair < int , long double > > , cmp > q ;
void dijkstra ( )   {
int nod ;
long double cost ;
q.push( mp ( 1 , 0 ) ) ;
d [ 1 ] = 0 ;
way [ 1 ] = 1 ;
vector < pair < int , long double > > :: iterator it ;
while ( !q.empty() )    {
nod = q.top().f;
cost = q.top().s ;
q.pop() ;
if ( d [ nod ] != cost ) continue ;
for ( it = v [ nod ].begin() ; it != v [ nod ].end() ; ++ it )  {
if ( d [ nod ] + (*it).s == d [ (*it).f ] || abs ( d [ nod ] + (*it).s - d [ (*it).f ] ) < ER ) {
way [ (*it).f ] += way [ nod ] ;
if ( way [ (*it).f ] > MOD )   way [ (*it).f ] -= MOD ;
}   else
if ( d [ nod ] + (*it).s < d [ (*it).f ] )  {
d [ (*it).f ] = d [ nod ] + (*it).s ;
q.push( mp ( (*it).f , d [ (*it).f ] ) ) ;
way [ (*it).f ] = way [ nod ] ;
}
}
}
}
int main () {
int i , j , x , y , z ;
in >> n >> m ;
while ( m -- )  {
in >> x >> y >> z ;
v [ x ].pb ( mp ( y , log ( z ) ) ) ;
v [ y ].pb ( mp ( x , log ( z ) ) ) ;
}
dijkstra() ;
for ( i = 2 ; i <= n ; ++ i )   out << way [ i ] << ' ' ;
}
``````