Cod sursa(job #3376438)

Utilizator zamhoriaHoria Zamfir zamhoria Data 17 noiembrie 2026 18:47:02
Problema Drumuri minime Scor 25
Compilator cpp-64 Status done
Runda Arhiva de probleme Marime 1.84 kb
#include <fstream>
#include <vector>
#include <queue>
#include <climits>
#include <cmath>

using namespace std;

ifstream cin("dmin.in");
ofstream cout("dmin.out");

const double INF = 1e18;

vector<double> dist; // dist[i] = dist. minima de la nodul 1 la nodul i
vector<int> drumuri; // nr de drumuri min
vector<vector<pair<int,long long>>> adj;

int n, m;

void dijkstra() {
    // tinem minte suma logaritmilor pt a evita overflow, -> log(a * b) = log(a) + log(b)
    // min heap in care tinem perechi de tipul {suma_logaritmilor, nod}
    priority_queue<pair<double,int>, vector<pair<double,int>>, greater<pair<double,int>>> pq;
    pq.push({0.0, 1});

    while (!pq.empty()) {
        auto [dist_curr, u] = pq.top();
        pq.pop();

        if (dist_curr > dist[u] + 1e-9) continue;

        for (auto [x, y] : adj[u]) {
            double dist_nou = dist_curr + log(y);

            // daca am gasit un drum mai scurt, resetam nr in dist
            if (dist_nou < dist[x]) {
                dist[x] = dist_nou;
                drumuri[x] = drumuri[u] % 104659;
                pq.push({dist[x], x});
            }else if (abs(dist_nou - dist[x]) <= 1e-9) {
                drumuri[x] = (drumuri[x] + drumuri[u]) % 104659;
            }
        }

    }
}

int main() {

    cin >> n >> m;

    dist.resize(n + 1, INF); // initiam cu -1
    drumuri.resize(n + 1, 0);
    adj.resize(n + 1);
    dist[1] = 0.0;
    drumuri[1] = 1;

    for (int i = 1; i <= m; i++) {
        int c1, c2;
        long long cost;

        cin >> c1 >> c2 >> cost;

        adj[c1].push_back({c2, cost});
        adj[c2].push_back({c1, cost});
    }

    dijkstra();

    for (int i = 2; i <= n; i++)
        if (dist[i] == INF)
            cout << 0 << " ";
        else cout << drumuri[i] << " ";

    return 0;
}