Dijkstra

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

using namespace std;

#define INF 1e9

struct arista
{
    int desde, hasta, costo;
};

struct par
{
    int nodo, dist;
};

bool operator<(const par &a, const par &b)
{
    ///Devolvemos si a.dist es mayor a b.dist
    ///porque priority_queue nos devuelve siempre el máximo
    ///entonces "hackeamos" la priority_queue
    ///haciendo que ordene al revés
    ///entonces siempre nos devolverá el mínimo
    return a.dist > b.dist;
}

vector <vector <arista> > ady;
int cantNodos; ///Esta variable es más útil si es global

vector <int> Dijkstra(int origen)
{
    vector <int> dist(cantNodos, INF);
    priority_queue <par> pq;
    dist[origen] = 0;
    pq.push({origen, 0});

    while(pq.size())
    {
        ///Saco el nodo con menor distancia
        int nodo = pq.top().nodo;
        pq.pop();

        ///Recorro los vecinos de nodo
        for(const auto &ar:ady[nodo])
        {
            if(dist[nodo]+ar.costo < dist[ar.hasta])
            {
                dist[ar.hasta] = dist[nodo]+ar.costo;
                pq.push({ar.hasta, dist[ar.hasta]});
            }
        }
    }

    return dist;
}

int main()
{
    int cantAristas, a, b, costo;
    cin >> cantNodos >> cantAristas;

    ady.resize(cantNodos+1);

    for(int i=0; i<cantAristas; i++)
    {
        cin >> a >> b >> costo;
        ady[a].push_back({a, b, costo});
        ady[b].push_back({b, a, costo});
    }

    vector <int> res = Dijkstra(1);

    cout << "Distancia desde el nodo 1 hacia los demas: " << endl;
    for(int i=1; i<=cantNodos; i++)
    {
        cout << i << ": " << res[i] << endl;
    }

    ///Ver este problema, es literal Dijkstra
    ///https://www.spoj.com/problems/EZDIJKST/

    ///Ver este problema, es Dijkstra con un agregado
    ///https://codeforces.com/problemset/problem/20/C
    ///Pide reconstruir el camino mínimo desde el nodo 1 hasta el nodo n
    ///Se puede lograr modificando un poco el código

    return 0;
}

/**
Ejemplo de input:
6 9
1 2 7
1 3 9
1 6 14
2 3 10
2 4 15
3 4 11
3 6 2
4 5 6
5 6 9

Output correcto:
Distancia desde el nodo 1 hacia los demas:
1: 0
2: 7
3: 9
4: 20
5: 20
6: 11

**/