Codeforces Round #584 (Div. 1 + Div. 2) F. Koala and Notebook (R2600)

勉強になった！！！！！
「辺番号または頂点番号が辞書順最小な最短路」を求める考え方が炸裂する感じ。

• 最短路として使われうる辺を列挙しておく (この考え方自体が典型)
• その辺をうまいこと活用しながら探索する

という典型の流れになっている。

問題へのリンク

問題概要

頂点数 、辺数 の無向グラフが与えられる。各頂点は と番号付けされていて、各辺は と番号付けされている。

さて、頂点 1 以外の各頂点 v について、頂点 1 から頂点 v へと至る経路をすべて考えたときの、その経路の番号を順に「文字列として連結」して得られる文字列を数値としてみたときの最小値を求めよ。

ただしその答えがとても大きくなる可能性があるので 1000000007 で割ったあまりで答えよ。

制約

• 
• 

考えたこと

例えば辺番号が順に、1, 64, 3, 999, 5 だったら、16439995 になるわけで、なんか桁数が異なるとすごく扱いづらい。。。(僕はこの時点で思考停止してしまった)

しかし、例えば 369 の辺は、3 の辺と 6 の辺と 9 の辺とに分解してしまえば OK。これをするメリットは

• 辺数が等しいパスでは、出来上がる整数の桁数も等しい

ということ。そして整数の大小関係は

• 桁数が小さいならば問答無用に小さい
• 桁数が等しいならば辞書順の小さい方が小さい

という関係にあることに注意する。よって問題は

---

各頂点へいたる経路に含まれる辺数が最小のもののうち、経路の辺ラベル列が辞書順最小のものを求めよ

---

ということになる。

辺数が最小のパスを列挙

辺数が最小のパスを列挙する方法は簡単。BFS を一度行って、

• dist[ v ] = dist[ u ] + 1 を満たす辺 e = (u, v) のみを採用する

と考えればよい。こういう最短路に含まれうる辺のみを考えるような考え方は典型。

こうすれば結局は最短路に含まれうる辺を列挙しておいて、その辺のみで構成されるグラフ上において「ラベル列が辞書順最小な経路を求める」という問題に帰着された。

ラベル列が辞書順最小となる経路の求め方

最後にラベル列が辞書順最小になる経路の求め方。基本的には DFS すればよいだけ。そして DFS 中の各頂点 v に対して隣接する頂点を適切な順序で訪問していけばよい。

基本的にはそれだけなのだが...

今回はちょっと罠がある。同一のラベル値をもつ辺の扱いが厄介だ。

上図のようなケースにおいて、頂点 A, B の優先順位は同等だが、先に頂点 A を DFS して、そのまま C, D を順に探索してしまうと、頂点 D のラベル値が "35" になってしまう。一方 C, D よりも先に B を探索しておいて

• (A, B) から出ている辺の重みが小さい順に探索

というポリシーで探索していれば、D のラベル値は "31" になる。つまり

• ラベル値が等しくなるような頂点はまとめて一つの頂点として探索して
• そのまとまった一つの頂点群から出ている辺のうち、重さが小さいところから順に探索していく

という方針で探索するとよい。

#include <iostream>
#include <vector>
#include <queue>
#include <algorithm>
using namespace std;

template<class T> inline bool chmax(T& a, T b) { if (a < b) { a = b; return 1; } return 0; }
template<class T> inline bool chmin(T& a, T b) { if (a > b) { a = b; return 1; } return 0; }

const int MOD = 1000000007;
using Edge = pair<int, long long>;
using Graph = vector<vector<Edge> >;

void dfs(const Graph &G, vector<int> vs, 
         vector<long long> &res, const vector<int> &dist) {
    for (int w = 0; w < 10; ++w) {
        vector<int> nvs;
        for (auto v : vs) {
            for (auto e : G[v]) {
                if (e.second != w) continue;
                if (dist[e.first] != dist[v] + 1) continue;
                if (res[e.first] != -1) continue;
                res[e.first] = (res[v] * 10 + e.second) % MOD;
                nvs.push_back(e.first);
            }
        }
        if (!nvs.empty()) dfs(G, nvs, res, dist);
    }
}

int main() {
    // 入力
    int N, M; cin >> N >> M;
    Graph G(N + M*6);
    int iN = N;
    for (long long w = 1; w <= M; ++w) {
        int u, v; cin >> u >> v; --u, --v;
        vector<int> nodes;
        nodes.push_back(u);
        long long w2 = w;
        while (w2 >= 10) {
            w2 /= 10;
            nodes.push_back(N++);
        }
        nodes.push_back(v);
        w2 = w;
        int s = (int)nodes.size();
        for (int i = 0; i+1 < s; ++i) {
            G[nodes[s-i-2]].push_back({nodes[s-i-1], w2 % 10});
            G[nodes[i+1]].push_back({nodes[i], w2 % 10});
            w2 /= 10;
        }
    }
    for (int v = 0; v < N; ++v) {
        sort(G[v].begin(), G[v].end(), [&](Edge a, Edge b) {
                return a.second < b.second;});
    }

    // 幅優先探索
    vector<int> dist(N, -1);
    queue<int> que;
    que.push(0); dist[0] = 0;
    while (!que.empty()) {
        auto v = que.front(); que.pop();
        for (auto e : G[v]) {
            if (dist[e.first] == -1) {
                dist[e.first] = dist[v] + 1;
                que.push(e.first);
            }
        }
    }

    // 最短路に使われる辺のみを使って辞書順最小 DFS
    vector<long long> res(N, -1);
    res[0] = 0;
    dfs(G, {0}, res, dist);
    for (int i = 1; i < iN; ++i) cout << res[i] << endl;
}