# Cod sursa(job #2432362)

Utilizator Data 23 iunie 2019 12:22:22 Drumuri minime 100 cpp-64 done Arhiva de probleme 1.33 kb
``````#include <fstream>
#include <cmath>
#include <queue>
#include <vector>

#define pp pair<int, int>

using namespace std;

ifstream fin("dmin.in");
ofstream fout("dmin.out");

const int NMax = 1500, oo = 1e9, MOD = 104659;
const double E = 1e-8;

int N, M, DP[NMax + 5];

vector <pair<int, double> > G[NMax + 5];
priority_queue <pp, vector<pp>, greater<pp> > Q;

double D[NMax + 5];

void Dijkstra(int Nod)
{
for(int i = 2; i <= N; i++)
D[i] = oo;

Q.push({0, 1}), DP[1] = 1;

while(!Q.empty())
{
Nod = Q.top().second;

for(auto Vecin : G[Nod])
{
int A = Vecin.first;
double C = Vecin.second;

if(D[A] == oo)
D[A] = D[Nod] + C, Q.push({D[A], A});
else
{
if(fabs(D[A] + C - D[Nod]) < E)
DP[Nod] = (DP[Nod] + DP[A]) % MOD;
}
}
Q.pop();
}
}

int main()
{
fin >> N >> M;

for(int i = 1, a, b; i <= M; i++)
{
double c;
fin >> a >> b >> c; c = log2(c);

G[a].push_back({b, c});
G[b].push_back({a, c});
}
Dijkstra(1);

for(int i = 2; i <= N; i++)
fout << DP[i] << " ";

fout << '\n';

fin.close();
fout.close();

return 0;
}
``````