Dijsktra

#include <algorithm>
#include <iostream>
#include <queue>
#include <utility>
#include <vector>
#include <cstdint>

using namespace std;

#define DISTANCE_INITIALIZATION_VALUE -1

void add_edge_directed(
    vector<vector<pair<std::int64_t, std::int64_t>>> &G,
    std::int64_t u,
    std::int64_t v,
    std::int64_t weight
) {
    G.at(u).push_back(make_pair(v, weight));
    // G.at(v).push_back(make_pair(u, weight));
}

class Compare {
   public:
    // Ringraziamo l'umile dipendente cicciottello
    // per aver scoperto la necessitá di una inspiegabile parentesi tonda
    bool operator() (
      pair<std::int64_t, std::int64_t> &lhs,
      pair<std::int64_t, std::int64_t> &rhs
    ) {
        return lhs.second > rhs.second;
    }
};

int main() {
    freopen("input.txt", "r", stdin);
    freopen("output.txt", "w", stdout);

    std::int64_t V, E;
    cin >> V >> E;
    vector<vector<pair<std::int64_t, std::int64_t>>> G(
        V,
        vector<pair<std::int64_t, std::int64_t>>()
    );

    std::int64_t source, destination;
    cin >> source >> destination;
    source--;
    destination--;

    for (std::int64_t edge = 0; edge < E; edge++) {
        std::int64_t u, v, w;
        cin >> u >> v >> w;
        u--;
        v--;
        add_edge_directed(G, u, v, w);
    }

    // Shortest path
    priority_queue<pair<std::int64_t, std::int64_t>, vector<pair<std::int64_t, std::int64_t>>, Compare> queue;

    queue.push(make_pair(source, 0));

    vector<bool> visited(V, false);
    vector<std::int64_t> distances(V, DISTANCE_INITIALIZATION_VALUE);

    while (!queue.empty()) {
        pair<std::int64_t, std::int64_t> curr = queue.top();
        queue.pop();

        if (!visited.at(curr.first)) {
            visited.at(curr.first) = true;
            distances.at(curr.first) = curr.second;

            for (pair<std::int64_t, std::int64_t> neighbour : G.at(curr.first)) {
                if (!visited.at(neighbour.first)) {
                    queue.push(make_pair(neighbour.first, curr.second + neighbour.second));
                }
            }
        }
    }

    cout << distances.at(destination);
    return 0;
}