#include<vector>
#include<deque>
#include<tuple>
#include<queue>

struct DijkstraGraph {
    struct Node;
    struct Arc {
        Node* dest;
        int l;
    };
    struct Node {
        std::vector<Arc> arc;
        bool explr = false;
        long long dist;
    };
    std::deque<Node> nodes;
    
    Node* add_node() {
        nodes.push_back(Node());
        return &nodes.back();
    }
    void add_edge(Node* u, Node* v, int l) {
        u->arc.push_back({v, l});
    }
    
    void dijkstra(Node* start) {
        std::priority_queue<std::pair<long long, Node*> > frontier;
        frontier.push({0, start});
        
        while(frontier.size() > 0) {
            long long potential;
            Node* cur;
            std::tie(potential, cur) = frontier.top();
            potential = -potential;
            frontier.pop();
            
            if(!cur->explr) {
                cur->explr = true;
                cur->dist = potential;
                
                for(Arc curArc : cur->arc) {
                    // priority_queue is a max-heap, so for convenience we use the negative of potential instead of
                    // defining a custom ordering function
                    frontier.push({-potential - curArc.l, curArc.dest});
                }
            }
        }
    }
};

int main() {
    DijkstraGraph graph;
    
    graph.add_node();
    graph.add_node();
    graph.add_edge(&graph.nodes[0], &graph.nodes[1], 5);
    // ...
    // Populate the graph with add_node and add_edge
    
    graph.dijkstra(&graph.nodes[0]); // Assumes node 0 is where we start the search
}