# Cod sursa(job #2443020)

Utilizator Data 26 iulie 2019 11:26:13 Drumuri minime 5 cpp-64 done Arhiva de probleme 1.36 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});
}
for(q.push({1, 0}); !q.empty(); q.pop()){
pair<int, double> node=q.top(); if(dmin[node.first]<node.second) continue;
for(auto i:graph[node.first]){
if(dmin[i.first]!=INT_MAX && dmin[i.first]==dmin[node.first]+i.second) {++sol[i.first]; q.push({i.first, dmin[i.first]});}
else if(dmin[i.first]>dmin[node.first]+i.second){
sol[i.first]=1;
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;
}
``````