Cod sursa(job #3376430)

Utilizator zamhoriaHoria Zamfir zamhoria Data 17 noiembrie 2026 18:32:00
Problema Drumuri minime Scor 0
Compilator cpp-64 Status done
Runda Arhiva de probleme Marime 1.51 kb
#include <bits/stdc++.h>

using namespace std;

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

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

int n, m;

void dijkstra() {

    // min heap in care tinem perechi de tipul {dist_min, nod}
    priority_queue<pair<int,int>, vector<pair<int,int>>, greater<pair<int,int>>> pq;
    pq.push({1, 1});

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

        if (dist_curr > dist[u]) continue;

        for (auto [x, y] : adj[u]) {
            long long dist_nou = dist_curr * 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];
                pq.push({dist[x], x});
            }else if (dist_nou == dist[x]) {
                drumuri[x] += drumuri[u];
            }
        }

    }
}

int main() {

    cin >> n >> m;

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

    for (int i = 1; i <= m; i++) {
        int c1, c2, 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++)
        cout << drumuri[i] % 104659 << " ";

    return 0;
}