Bubble Cup 8 - Finals G. Run for beer

問題文

http://codeforces.com/contest/575/problem/G

解法

1ステップごとにコストが10倍になり、かつ辺のコストは高々9であることから、通った道を前から見て10進表記したものがコストなので、できるだけ短いほうがいいことにはすぐ気がつく。

同じ長さならコストが小さいほうがいいが、コストを保持してダイクストラは不可能なので面倒。
とりあえず、今の（これまでに移動した回数、直前の辺のコスト）で最短経路問題を解き、最短路グラフもどきを作る。直前の辺のコストしか見ていないから、真の最短路ではない辺も含まれている。

あとは最短路グラフ（もどき）の上でゴールから1ステップずつみていって、その時々で一番小さいコストの辺を使う頂点以外を取り除いていき、頂点0までたどり着けた頂点が真の最短路になる。

もう一つ面倒なのが、コスト0の辺があることで、こいつのせいで leading zero をいい感じに処理しないといけなくなる。というのも、0がたくさん頭につくときに、これまでに移動した回数をカウントしてしまうと、実際は0なのに最短路グラフ（もどき）に含まれなくなるからである。かといって0のときにカウントしない、みたいなこともできない。

なので、あらかじめ頂点 n - 1 からコスト0だけを使って辿れるところを BFS で列挙しておく（BFSじゃないとパスの長さの最小化にならないので注意）。ここでも最短路グラフを作っておく。

さっきの始点から始める最短経路計算のゴールを、頂点 n - 1 じゃなくて、このBFSで辿れた頂点のうちのどこでもよい、とする。

最後に、その頂点まで至る最短路と、その頂点から終点までに至る最短路を別に復元すればOK。

計算量は O(mlogn + n) 。ダイクストラしてるからね。

ソースコード

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

using ll = long long;
using pii = pair<int, int>;

constexpr int inf = 1e9;

struct edge {
    int to, cost;
};

using graph = vector<vector<edge>>;

int main() {
    int n, m; cin >> n >> m;
    graph g(n);
    for(int i = 0; i < m; ++i) {
        int a, b, c; cin >> a >> b >> c;
        g[a].push_back(edge{b, c});
        g[b].push_back(edge{a, c});
    }
    vector<int> to(n, -1), len(n, inf);
    {
        queue<int> que;
        que.push(n - 1);
        len[n - 1] = 0;
        while(!que.empty()) {
            const auto v = que.front(); que.pop();
            for(auto& e : g[v]) {
                if(e.cost != 0 || len[e.to] != inf) continue;
                to[e.to] = v;
                len[e.to] = len[v] + 1;
                que.push(e.to);
            }
        }
    }

    using S = tuple<int, int, int, int>;
    priority_queue<S, vector<S>, greater<>> que;
    que.emplace(0, 0, len[0], 0);
    vector<pii> d(n, make_pair(inf, inf));
    d[0] = make_pair(0, 0);
    vector<vector<pii>> prev(n);
    int last_v = -1;
    while(!que.empty()) {
        int dn, pre_d, zero_len, v;
        tie(dn, pre_d, zero_len, v) = que.top(); que.pop();
        if(d[v] < make_pair(dn, pre_d)) continue;
        if(to[v] != -1 || v == n - 1) { // answer
            last_v = v;
            break;
        }
        for(auto& e : g[v]) {
            if(d[e.to] > make_pair(dn + 1, e.cost)) {
                d[e.to] = make_pair(dn + 1, e.cost);
                prev[e.to].clear();
                prev[e.to].emplace_back(v, e.cost);
                que.emplace(dn + 1, e.cost, len[e.to], e.to);
            } else if(d[e.to] == make_pair(dn + 1, e.cost)) {
                prev[e.to].emplace_back(v, e.cost);
            }
        }
    }

    string ans;
    vector<int> cur = {last_v}, prev2(n, -1);
    while(!cur.empty()) {
        int mini = 10;
        vector<int> nxt;
        for(auto v : cur) {
            for(auto& p : prev[v]) {
                if(mini > p.second) {
                    mini = p.second;
                    nxt.clear();
                    nxt.push_back(p.first);
                    prev2[p.first] = v;
                } else if(mini == p.second) {
                    prev2[p.first] = v;
                    nxt.push_back(p.first);
                }
            }
        }
        if(mini != 10) {
            ans += mini + '0';
        }
        cur = move(nxt);
    }
    if(ans.empty()) ans = "0";
    vector<int> path;
    {
        int now = 0;
        while(now != -1) {
            path.push_back(now);
            now = prev2[now];
        }
        now = last_v;
        while(to[now] != -1) {
            path.push_back(to[now]);
            now = to[now];
        }
    }

    const int sz = path.size();
    cout << ans << endl;
    cout << sz << endl;
    for(int i = 0; i < sz; ++i) {
        cout << path[i] << " \n"[i + 1 == sz];
    }
}

感想

公式解説だと O(n + m) らしい。すごいね。
無限にバグって辛かった（めんどくさいことが多すぎる）。