Cod sursa(job #2443069)

Utilizator Data 26 iulie 2019 12:47:04 Drumuri minime 100 cpp-64 done Arhiva de probleme 1.34 kb
``````#include <iostream>
#include <cmath>
#include <cstdio>
#include <queue>
#include <climits>
#include <vector>
using namespace std;
int n, m, i, j, sol[1501];
double dmin[1501];
vector<pair<int, double> > graph[1501];
struct comp{
bool operator()(pair<int, double> x, pair<int, double> y){
return dmin[x.first]>dmin[y.first];
}
};
priority_queue<pair<int, double>, vector<pair<int, double> >, comp> q;
int main()
{
freopen("dmin.in", "r", stdin);
freopen("dmin.out", "w", stdout);
scanf("%d%d", &n, &m);
for(i=2; i<=n; ++i) dmin[i]=INT_MAX;
for(i=1; i<=m; ++i){
int x, y; double z;
scanf("%d%d%lf", &x, &y, &z); z=log2(z);
graph[x].push_back({y, z});
graph[y].push_back({x, z});
}
sol[1]=1;
for(q.push({1, 0}); !q.empty(); q.pop()){
pair<int, double> node=q.top();
for(auto i:graph[node.first]){
if(dmin[i.first]!=INT_MAX && fabs(dmin[i.first]-dmin[node.first]+i.second)<0.0000001) {
sol[node.first]=(sol[i.first]+sol[node.first])%104659;
}
else if(dmin[i.first]==INT_MAX){
dmin[i.first]=dmin[node.first]+i.second;
q.push({i.first, dmin[i.first]});
}
}
}
for(i=2; i<=n; ++i) printf("%d ", sol[i]);
return 0;
}
``````