Disjkstra

dijkstra.cpp

#include <iostream>
#include <list>
#include <queue>
#include <memory>
#include <limits>
#include <vector>
#include <unordered_map>
#include <functional>
#include <locale>
#include <list>

using std::cout, std::cin;

struct Node;
using NodePtr = std::shared_ptr<Node>;
using Vector = std::vector<NodePtr>;
using List = std::list<NodePtr>;

struct Node {
    std::string label;
    Vector adj;
    double dist = std::numeric_limits<double>::max();
    NodePtr prev = nullptr;
    bool closed = false;
    Node(const std::string label): label(label){}
};

using QueueCmp = std::function<bool(NodePtr, NodePtr)>;
using Queue = std::priority_queue<NodePtr, Vector, QueueCmp>;
using Graph = std::unordered_map<std::string, NodePtr>;
using Weight = std::unordered_map<std::string, std::unordered_map<std::string, int>>;

struct Delimiter: std::ctype<char> {
    static mask* make_table(const std::string& ds) {
        static std::vector<mask> table(classic_table(),
                                       classic_table() + table_size);
        for (auto m: table) {
            m &= ~space;
        }
        for (auto d: ds) {
            table[d] |= space;
        }
        return &table[0];
    }
    Delimiter(const std::string& ds, size_t refs = 0):
        ctype(make_table(ds), false, refs) {}
};

void add_entry(Graph& g, const std::string& label) {
    if (g.find(label) == g.end()) {
        g[label] = std::make_shared<Node>(label);
    }
}

auto read_input(std::istream& in, std::string& src, std::string& dst) {
    Graph g; Weight w;
    cin.imbue(std::locale(cin.getloc(), new Delimiter(":")));
    in >> src >> dst;
    std::string from, to;
    int weight;
    while (in >> from >> weight >> to) {
        add_entry(g, from); add_entry(g, to);
        w[from][to] = weight;
        g[from]->adj.push_back(g[to]);
    }
    return std::make_pair(g, w);
}

void dijkstra(Graph& g,
              Weight& w,
              const std::string& src,
              const std::string& dst) {
    Queue q([](NodePtr a, NodePtr b) {
        return a->dist > b->dist;
    });
    g[src]->dist = 0;
    q.push(g[src]);
    while (!q.empty()) {
        NodePtr u = q.top(); q.pop();
        u->closed = true;
        for (NodePtr v: u->adj) {
            if (v->closed) continue;
            int new_weight = u->dist + w[u->label][v->label];
            if (new_weight < v->dist) {
                v->dist = new_weight;
                v->prev = u;
                q.push(v);
            }
        }
    }
}

List shortest_path(NodePtr dst) {
    List result;
    NodePtr aux = dst;
    while (aux != nullptr) {
        result.push_front(aux);
        aux = aux->prev;
    }
    return result;
}

std::ostream& operator<<(std::ostream& os, const NodePtr node) {
    os << "[";
    os << node->label
        << ", " << node->dist
    ;
    os << "]";
    return os;
}

std::ostream& operator<<(std::ostream& os, const List& l) {
    os << "(";
    size_t i = 0;
    for (auto& node: l) {
        os << node;
        if (i++ < l.size() - 1) os << "->";
    }
    os << ")";
    return os;
}

std::ostream& operator<<(std::ostream& os, const Graph& g) {
    os << "(";
    size_t i = 0;
    for (auto& [key, value]: g) {
        os << value->label;
        if (i < g.size() - 1) os << ", ";
    }
    os << ")";
    return os;
}

int main() {
    std::string src, dst;
    auto [g, w] = read_input(std::cin, src, dst);
    dijkstra(g, w, src, dst);
    cout << shortest_path(g[dst]) << '\n';
    return 0;
}