Pagini recente » Cod sursa (job #114590) | Cod sursa (job #1865950)
#include<fstream>
#include<vector>
#include<cmath>
#include<cstring>
#include<queue>
#define MOD 104659
#define EPS 0.0000000001
#define INF 20000000000.0
using namespace std;
ifstream fin("dmin.in");
ofstream fout("dmin.out");
int n, m, a, b, c;
vector< pair<int, double> > v[1505];
double d[1505];
int cnt[1505];
priority_queue< pair< double, int >, vector< pair< double, int > >, greater< pair< double, int > > > q;
int main(){
fin >> n >> m;
for( int i = 1; i <= m; i++ ){
fin >> a >> b >> c;
v[a].push_back( make_pair( b, log(c) ) );
v[b].push_back( make_pair( a, log(c) ) );
}
for( int i = 2; i <= n; i++ ){
d[i] = INF;
cnt[i] = 0;
}
cnt[1] = 1;
q.push( make_pair( 0, 1 ) );
while( !q.empty() ){
int nod = q.top().second;
int y = q.size();
for( int i = 0; i < v[nod].size(); i++ ){
int vecin = v[nod][i].first;
double cost = v[nod][i].second;
if( d[vecin] - ( d[nod] + cost ) > EPS ){
d[vecin] = d[nod] + cost;
cnt[vecin] = cnt[nod];
q.push( make_pair( d[vecin], vecin ) );
}else{
if( d[vecin] - (d[nod] + cost) <= EPS && d[vecin] - (d[nod] + cost) >= -EPS ){
cnt[vecin] = ( cnt[vecin] + cnt[nod] ) % MOD;
if( cnt[vecin] < 0 ){
cnt[vecin] += MOD;
}
}
}
}
q.pop();
}
for( int i = 2; i <= n; i++ ){
fout << cnt[i] << " ";
}
return 0;
}