両側ダイクストラによる二点間最短路 (有向グラフ対応)

Graph makeReversed(const Graph &g) {
    int n = g.size();
    Graph revg(n);
    for (auto &es : g) {
        for (auto &e : es) {
            Edge re = e;
            std::swap(re.src, re.dst);
            revg[re.src].push_back(re);
        }
    }
    return revg;
}

Weight bidirectionalDijkstraImpl(const Graph &g, const Graph &rg, int s, int t) {
    int n = g.size();

    using State = std::pair<Weight, int>;
    std::priority_queue<State, std::vector<State>, std::greater<State>> pq[2];
    pq[0].emplace(0, s);
    pq[1].emplace(0, t);

    constexpr Weight INF = std::numeric_limits<Weight>::max() / 8;
    std::vector<Weight> dist[2];
    dist[0] = dist[1] = std::vector<Weight>(n, INF);
    dist[0][s] = dist[1][t] = 0;

    const Graph *gs[2] = {&g, &rg};

    Weight mu = INF;
    while (pq[0].size() && pq[1].size()) {
        if (pq[0].top().first + pq[1].top().first >= mu) break;
        int k = pq[0].top().first <= pq[1].top().first ? 0 : 1;
        Weight d;
        int v;
        std::tie(d, v) = pq[k].top();
        pq[k].pop();
        if (d < dist[k][v]) continue;
        for (auto &e : (*gs[k])[v]) {
            Weight w = e.dst;
            if (dist[k][w] > dist[k][v] + e.weight) {
                dist[k][w] = dist[k][v] + e.weight;
                pq[k].emplace(dist[k][w], w);
                mu = std::min(mu, dist[k][v] + e.weight + dist[1 - k][w]);
            }
        }
    }
    return mu;
}

Weight bidirectionalDijkstra(const Graph &g, int s, int t, bool dir) {
    if (s == t) return 0;
    if (dir) {
        Graph revg = makeReversed(g);
        return bidirectionalDijkstraImpl(g, revg, s, t);
    } else {
        return bidirectionalDijkstraImpl(g, g, s, t);
    }
}