chat.cpp

#include <vector>
#include <queue>
#include <limits>
#include <algorithm>

using namespace std;

#define pdn pair<long long, int>    // pdn = pair<distance, nodo>

struct comparison {
    bool operator() (const pdn& a, const pdn& b) {
        return a.first > b.first || 
        (a.first == b.first && a.second > b.second);    // non essenziale per alg, solo per completezza
    }
};

void mincammino(int N, int M, vector<int> X, vector<int> Y, vector<int> P, vector<long long>& D) {
    vector<vector<pair<int, int>>> adj(N); // adj[u] = {v, peso}
    
    // Costruzione del grafo
    for (int i = 0; i < M; ++i) {
        adj[X[i]].emplace_back(Y[i], P[i]);
    }

    fill(D.begin(), D.end(), -1);
    D[0] = 0;

    vector<bool> visited(N, false);
    
    priority_queue<pdn, vector<pdn>, comparison> pq;

    pq.emplace(0, 0); // {distanza, nodo}

    while (!pq.empty()) {
        auto [dist, u] = pq.top();
        pq.pop();
        
        if (visited[u]) continue;
        visited[u] = true;

        for (auto [v, weight] : adj[u]) {
            if (D[v] == -1 || D[v] > dist + weight) {
                D[v] = dist + weight;
                pq.emplace(D[v], v);
            }
        }
    }
}