Yosupo Library Checker - Shortest Path

Library Checker というと難しいイメージがあるけど、この問題のように基本的な問題もある。でも、「最短路の復元」を要求する問題は意外と少ないので、とても貴重な問題！

• 問題へのリンク

問題概要

頂点数 、辺数 の単純な重み付き有向グラフが与えられる。各辺の重みは非負である。

頂点 から頂点 へと至る最短経路を 1 つ求めて、出力せよ。

制約

• 
• 

考えたこと

Dijkstra 法そのものは、けんちょん本にも書いているし、蟻本にも書いてあるし、鉄則本にも書いてあるし、アルゴリズムに関する本ならほとんど書いてある。ここではそれについては省略する。

今回の問題の特徴は、頂点 から頂点 へと至る最短経路の長さを求めるだけでなく、最短経路そのものを求めることを要求されている。

これを通称「経路復元」または「復元」と呼ぶ。復元の方法論については、次の Qiita 記事に書いた。

qiita.com

今回の問題に対しても、この Qiita 記事で書いたように、次の配列 prev を用意して解くことができる。

---

prev[v] ← 頂点 から頂点 へと至る最短経路における、頂点 の直前の頂点

---

コード

#include <bits/stdc++.h>
using namespace std;


// Edge
template<class T> struct Edge {
    int to;
    T weight;
    Edge(int t, T w) : to(t), weight(w) {}
};

// Graph
template<class T> struct Graph : vector<vector<Edge<T>>> {
    Graph() {}
    Graph(int N) : vector<vector<Edge<T>>>(N) {}
};

// Dijkstra, find {dp, prev}
// dp[v] := length of the shortest s-v path
// prev[v] := previous node of node v on the shortest path
template<class T> pair<vector<T>, vector<int>> Dijkstra(const Graph<T> &G, int s) {
    // Dijkstra 法実行のための変数
    vector<T> dp(G.size(), numeric_limits<T>::max());
    vector<int> prev(G.size(), -1);
    using Node = pair<T, int>;
    priority_queue<Node, vector<Node>, greater<Node>> que;
    
    // 初期条件
    dp[s] = 0;
    que.push(Node(0, s));
    
    // Dijkstra 法
    while (!que.empty()) {
        const auto [cur, v] = que.top();
        que.pop();
        
        // 枝刈り
        if (cur > dp[v]) continue;
        
        // 各辺への遷移を試す
        for (const auto &e : G[v]) {
            if (dp[e.to] > dp[v] + e.weight) {
                dp[e.to] = dp[v] + e.weight;
                prev[e.to] = v;
                que.push(Node(dp[e.to], e.to));
            }
        }
    }
    return make_pair(dp, prev);
}

// reconstruct the shortest path by using prev
vector<int> reconstruct(const vector<int> &prev, int s, int t) {
    vector<int> res;
    int v = t;
    do {
        res.push_back(v);
        v = prev[v];
    } while (v != s && v != -1);
    res.push_back(s);
    reverse(res.begin(), res.end());
    return res;
}
    
void Yosupo_Shortest_Path() {
    int N, M, s, t;
    cin >> N >> M >> s >> t;
    Graph<long long> G(N);
    for (int i = 0; i < M; ++i) {
        int a, b, c;
        cin >> a >> b >> c;
        G[a].emplace_back(b, c);
    }
    
    const auto [dp, prev] = Dijkstra(G, s);
    const auto &path = reconstruct(prev, s, t);
    
    if (prev[t] == -1) cout << -1 << endl;
    else {
        cout << dp[t] << " " << path.size()-1 << endl;
        for (int i = 0; i+1 < path.size(); ++i) {
            cout << path[i] << " " << path[i+1] << endl;
        }
    }
}

int main() {
    Yosupo_Shortest_Path();
}