main.cpp

#include <iostream>
#include <vector>
#include <queue>
#include <list>
#include <unordered_map>

typedef std::vector<std::list<int>> AdjacencyList;
typedef std::unordered_map<int, std::unordered_map<int, size_t>> Weights;

std::pair<std::vector<int>, std::vector<size_t>> dijkstra(AdjacencyList &adj, Weights weights, int src) {
    size_t n = adj.size();
    
    std::vector<int> prev(n, -1);
    std::vector<size_t> dist (n, INT_MAX);
    std::vector<bool> visited(n, false);
    
    auto comp = [&dist](const int& lhs, const int& rhs) -> bool { return dist[lhs] > dist[rhs]; };
    std::priority_queue<int, std::vector<int>, decltype(comp)> candidates(comp);
    
    candidates.push(src);
    dist[src] = 0;
    while (!candidates.empty()) {
        int next = candidates.top();
        candidates.pop();
        
        if (visited[next]) {
            continue;
        }
        
        visited[next] = true;
        
        for(std::list<int>::const_iterator it = adj[next].begin(); it != adj[next].end(); it++) {
            int neighbor = *it;
            
            if (dist[neighbor] == INT_MAX || (dist[next] + weights[next][neighbor] < dist[neighbor])) {
                dist[neighbor] = dist[next] + weights[next][neighbor];
                prev[neighbor] = next;
                candidates.push(neighbor);
            }
        }
    }
    
    return std::pair<std::vector<int>, std::vector<size_t>>(prev, dist);
}

int main() {
    std::vector<std::list<int>> adj;
    
    int a  = 0;
    int b1 = 1;
    int b2 = 2;
    int c  = 3;
    int d1 = 4;
    int d2 = 5;
    int e  = 6;
    
    std::list<int> adj_a;
    adj_a.push_back(b1);
    adj_a.push_back(b2);
    
    std::list<int> adj_b1;
    adj_b1.push_back(c);
    
    std::list<int> adj_b2;
    adj_b2.push_back(c);
    adj_b2.push_back(d2);
    
    std::list<int> adj_c;
    adj_c.push_back(d1);
    adj_c.push_back(d2);
    
    std::list<int> adj_d1;
    adj_d1.push_back(e);
    
    std::list<int> adj_d2;
    adj_d2.push_back(e);
    
    std::list<int> adj_e;
    
    adj.emplace_back(adj_a);
    adj.emplace_back(adj_b1);
    adj.emplace_back(adj_b2);
    adj.emplace_back(adj_c);
    adj.emplace_back(adj_d1);
    adj.emplace_back(adj_d2);
    adj.emplace_back(adj_e);
    
    std::unordered_map<int, std::unordered_map<int, size_t>> w;
    
    w[a][b1] = 3;
    w[a][b2] = 1;
    w[b1][c] = 2;
    w[b2][c] = 1;
    w[c][d1] = 7;
    w[c][d2] = 5;
    w[d1][e] = 2;
    w[d2][e] = 3;
    w[b2][d2] = 10;
    
    std::pair<std::vector<int>, std::vector<size_t>> data = dijkstra(adj, w, a);
    std::cout << data.second[e] << "\n";
}