dijkstra

#include <iostream>
#include <fstream>
#include <vector>
#include <stdlib.h>
#include <algorithm>
#include <cstring>
#include <queue>


#define INF 2147483647

using namespace std;

int N;

int dijkstra(vector<vector<pair<int, int>>> adj, int start, int goal)
{
    vector<unsigned int> distanza (N, INF);

    /* Coda contenente i nodi in lavorazione */
    priority_queue<
            pair<int, int>,
            vector<pair<int, int>>,
            greater<pair<int, int>> > pq;

    vector<bool> solved(N, false);

    distanza[start] = 0;
    solved[start] = true;
    pq.push({0, start});

    /* Finché ci sono nodi in coda */
    while (!pq.empty()) {
        pair<int, int> current = pq.top();
        pq.pop();

        int cn = current.second;
        int cc = current.first;
        solved[cn] = true;

        /* Controllo i nodi adiacenti */
        for (vector<pair<int, int>>::iterator it = adj[cn].begin(); it != adj[cn].end(); it++) {
            int i = it->first;
            int partial_cost = it->second;

            /* Se è già stato marcato come risolto lo salto */
            if (solved[i]) continue;

            int new_cost = cc + partial_cost;

            /* Se il costo per accedere da questo nodo è minore, lo riaggiungo alla coda */
            if (new_cost < distanza[i]) {
                distanza[i] = new_cost;
                pq.push({distanza[i], i});
            }
        }

    }
    return distanza[goal];

}


int main() {

    int A;
    int S, D;
    ifstream input("input.txt");
    ofstream output("output.txt");

    input >> N >> A;
    input >> S >> D;

    vector< vector< pair<int, int> > > adj (N);
    for (int i = 0; i < N; i++) {
        vector<pair<int, int>> v;
        adj[i] = v;
    }

    for (int i = 0; i < A; i++) {
        int source, dest, cost;
        input >> source >> dest >> cost;
        adj[source-1].push_back(make_pair(dest-1, cost));
        //adj[dest-1].push_back(make_pair(source-1, cost));
    }

    int ret = dijkstra(adj, S-1, D-1);


    output << ret;
    output.close();

    return 0;
}