#include <climits>
#include <iostream>
#include <set>
#include <vector>
using namespace std;

// spravíme si struct na uloženie hrany:
// "to" je kam vedie, "length" je jej dĺžka

struct edge { int to, length; };

// funkcia dijkstra() vráti dĺžku najkratšej cesty v grafe "graph"
// z vrcholu "source" do vrcholu "target"

// v "graph" musia mať všetky hrany nezáporné dĺžky

// všimnite si odovzdanie parametru "graph" const-referenciou, aby sa 
//     zbytočne nekopíroval

int dijkstra(const vector< vector<edge> > &graph, int source, int target) {

	// inicializácia: vzdialenosť "source" je 0, ostatné vrcholy nekonečno
    vector<int> min_distance( graph.size(), INT_MAX );
    min_distance[ source ] = 0;
    
    // active_vertices je množina obsahujúca záznamy tvaru "(d,v)"
    //     kde "v" je ešte nespracovaný vrchol 
    //     a "d" je doteraz najlepšia známa vzdialenosť zo "source" do "v"

    // keďže set<> v C++ je usporiadaný, je táto množina usporiadaná primárne
    //     podľa vzdialenosti od "source"

    set< pair<int,int> > active_vertices;
    active_vertices.insert( {0,source} );
    
    // dokola opakujeme:
    //     vyber nespracovaný vrchol najbližší ku "source"
    //     tento vrchol je odteraz definitívne spracovaný
    //     prejdi všetky hrany z neho a skús zmenšiť vzdialenosti do susedov

    while (!active_vertices.empty()) {

    	// zisti, ktorý vrchol ideme spracúvať
	    int where = active_vertices.begin()->second;

	    // ak je to "target", sme hotoví
    	if (where == target) return min_distance[where];

    	// zmaž jeho záznam spomedzi vrcholov čakajúcich na spracovanie
    	active_vertices.erase( active_vertices.begin() );

    	// prejdi všetky hrany vychádzajúce z "where"
    	for (const auto &ed : graph[where])
    	    // pozri, či touto hranou niečo zlepšíme
    		if (min_distance[ed.to] > min_distance[where] + ed.length) {
    			// ak vieme zlepšiť vzdialenosť do "ed.to", zmažeme starý
    			//     záznam o tomto vrchole ...
    			//     (ak mal doteraz min_distance == INT_MAX a teda ešte nemal
    			//     záznam v active_vertices, nič sa nezmaže)
    			active_vertices.erase( { min_distance[ed.to], ed.to } );
    			// ... zlepšíme mu zapamätanú vzdialenosť ... 
    			min_distance[ed.to] = min_distance[where] + ed.length;
    			// ... a vyrobíme o ňom nový záznam
    			active_vertices.insert( { min_distance[ed.to], ed.to } );
    		}
    	}

    // ak sme sa dostali až sem, cesta zo "source" do "target" neexistuje
    return INT_MAX;
}

int main() {
	// test na miniatúrnom grafe:
	// (0) ---1--> (1) ---1---> (2) ---1--> (3)
	//  \                                  /
	//   -----------------2--------------->
	
	vector< vector<edge> > graph = { { {1,1}, {3,2} }, { {2,1} }, { {3,1} }, { } };
	cout << dijkstra(graph,0,3) << endl; // vypíše 2
	cout << dijkstra(graph,0,2) << endl; // vypíše 2
	cout << dijkstra(graph,1,2) << endl; // vypíše 1
	cout << dijkstra(graph,2,0) << endl; // vypíše INT_MAX
}