Dijkstra + lectura de grafos ponderados

#include <iostream>
#include <vector>
#include <queue>

using namespace std;

#define INF (1 << 29)

vector <vector <pair<int, int> > > ady; ///Lista de adyacencia de grafo ponderado
int n; ///Cantidad de nodos

vector <int> Dijkstra(int inicio)
{
    vector <int> dist(n+1, INF);
    priority_queue <pair<int, int> > pq;

    ///Para comenzar el algoritmo decimos que dist[inicio] es cero
    ///Y ponemos el primer elemento junto con su distancia en la cola de prioridad

    dist[inicio] = 0;
    pq.push({0, inicio});

    ///Nota: por convención nuestra, siempre que usemos par, el first es el costo o distancia
    ///El second va a ser el nodo
    ///Esta convención se usa en la lista de adyacencia y en la cola de prioridad, para que sean coherentes

    for(int i=0; i<n; i++)
    {
        ///pq.top() me devuelve el pair con mayor prioridad (o sea el mas grande)
        ///http://www.cplusplus.com/reference/utility/pair/operators/
        ///Nota: no es necesario incluir utility
        int nodo = pq.top().second;
        pq.pop();

        for(int j=0; j<ady[nodo].size(); j++)
        {
            int vecino = ady[nodo][j].second;
            int costo = ady[nodo][j].first;

            if(dist[nodo] + costo < dist[vecino])
            {
                ///dist[nodo] + costo representa:
                ///la menor distancia desde inicio hasta nodo + costo de nodo hasta vecino
                ///Si entré acá significa que esa distancia nueva es mejor que lo que había antes
                ///entonces actualizo la distancia, y pongo al vecino con su distancia en pq
                dist[vecino] = dist[nodo] + costo;
                pq.push({-dist[vecino], vecino});
                ///------^ Notar el signo menos antes de la distancia
                ///eso lo usamos para que la cola de prioridad nos ordene por "menor distancia"
            }
        }

        ///El for i solo necesita ir hasta n ya que cada vez que sacamos algo de la cola de prioridad
        ///sabemos que su distancia ya es mínima, entonces como tenemos que procesar N nodos
        ///necesitamos n extracciones de la PQ
    }

    return dist; ///Devuelvo el vector con distancias calculadas. INF si no es posible llegar a X nodo
}

void lecturaGrafoPonderado()
{
    ///Esto no lo vimos en clase pero es fácil uniendo conceptos y recordando
    ///la lectura para grafos no ponderados

    int m;
    cin >> n >> m; ///Leo nodos y aristas

    ady.resize(n+1);

    for(int i=0; i<m; i++)
    {
        int desde, hasta, costo;
        cin >> desde >> hasta >> costo;
        ady[desde].push_back({costo, hasta});
        ady[hasta].push_back({costo, desde});
    }
}

int main()
{
    /**
    Input:
    6 7
    1 2 5
    1 4 9
    1 5 2
    2 3 2
    3 4 3
    4 6 2
    5 6 3
    1
    **/

    lecturaGrafoPonderado();

    int nodoInicio;
    cin >> nodoInicio;

    vector <int> distancias = Dijkstra(nodoInicio);

    cout << "Las distancias minimas desde " << nodoInicio << " son: " << endl;
    for(int i=1; i<=n; i++)
    {
        cout << nodoInicio << " -> " << i << ": ";
        if(distancias[i] == INF)
             cout << "Imposible llegar" << endl;
        else
            cout << distancias[i] << endl;
    }

    return 0;
}