Explicatie: algoritmul lui Dijkstra

/// priority_queue se afla in libraria <queue>

#include <fstream>
#include <queue>
#include <vector>

using namespace std;

ifstream in("dijkstra.in");
ofstream out("dijkstra.out");

const int MAX_N = 100000; /// Valoarea maxima pentru N.
const int INF = 0x7fffffff; /// Un truc, valoarea e scrisa in baza 16. Reprezinta cel mai mare numar care poate fi tinut pe int.

class Node { /// Clasa de care se va folosi priority_queue.
public: /// Daca nu faci astea publice, nu merge.
    int index; /// Indicele nodului.
    int dist; /// Distanta pana la nod pe care o tin in heap.

    bool operator <(const Node &other) const { /// Operatorul < pe care priority_queue il foloseste daca il gaseste in clasa.
        return this->dist > other.dist; /// Semnul e invers. Heapul sorteaza dupa astea, dar tine si indicele. Ca si cum ai sorta un struct.
    }
};

struct Edge { /// Edge : se tine minte pentru lista de adiacenta.
    int other; /// Vecinul nodului.
    int cost; /// Costul mucheiei.
};

int n, m; /// n, m din enuntul problemei.
int D[1 + MAX_N]; /// Distantele pana la noduri.
vector < Edge > adjList[1 + MAX_N]; /// Lista de adiacenta.
priority_queue < Node > Q; /// priority_queue, declarat simplu pe clasa Node, fiindca are operator de < incorporat.

void dijkstra(int s) {
    int u, d, v, c, i;

    for(i = 1; i <= n; i++) D[i] = INF; /// Setez distantele pe INF.
    D[s] = 0; /// Distanta pana la sursa este 0.
    Q.push(Node{s, 0}); /// Adaug in heap sursa.

    while(Q.empty() == false) { /// Cat timp inca mai am noduri in heap.
        u = Q.top().index; /// u este indicele nodului
        d = Q.top().dist; /// d este distanta pana la nodul cu distanta minima.
        Q.pop(); /// Scot minimul din heap.

        if(d == D[u]) { /// Verific daca nu cumva nodul era vechi si nu am nevoie de el.
            for(i = 0; i < adjList[u].size(); i++) { /// Trec prin toti vecinii.
                v = adjList[u][i].other; /// v este vecinul nodului u.
                c = adjList[u][i].cost; /// c este costul muchiei (u, v).

                if(D[v] > d + c) { /// Daca distanta pana la v curenta este mai mica decat d + c
                    D[v] = d + c; /// Distanta pana la v devine egala cu d + c
                    Q.push(Node{v, D[v]}); /// Introduc in heap v, cu distanta D[v].
                }
            }
        }
    }
}


int main() {
    int i, u, v, c;

    in >> n >> m;
    for(i = 1; i <= m; i++) {
        in >> u >> v >> c; /// Muchie orientata intre u si v, de cost c.
        adjList[u].push_back(Edge{v, c}); /// Veciunul este v, costul muchiei este c.
    }

    dijkstra(1); /// Pornim dijkstra cu sursa 1.
    for(i = 2; i <= n; i++) {
        if(D[i] == INF) {
            D[i] = 0; /// Respectam conditia din enunt - un nod la care nu s-a ajuns este marcat 0.
        }
        out << D[i] << ' ';

    }
    out << '\n';

    return 0;
}


/** Linkuri sumplimentare:
        1. priority_queue si ce face - http://www.cplusplus.com/reference/queue/priority_queue/
        2. algoritmul lui Dijkstra explicat si pe Wikipedia - https://en.wikipedia.org/wiki/Dijkstra%27s_algorithm
    Baga codul in Code::Blocks, se va vedea mai bine sintaxa.
*/