GCJ 2015 Round 1B A. Counter Culture

2015/05/03 (Sun) GCJ 貪欲 最短経路

問題

問題文

正整数に対して以下の操作を繰り返し行える。

  • 1 加算する
  • 文字列と見て前後反転する。leading-zero が生じた時は無視する

整数の $1$ を $N$ にするのに必要な操作の回数の最小値を求めなさい。

方針

移動可能な整数間に有向辺を張ったグラフを構築し、ダイクストラ法で最短路を求める。 しかしこれでは Small しか解けない…

実装

void dijk(Graph const&g, int s, vector<Weight> &dist, vi &prev) {
    int n = g.size();
    dist.assign(n, inf); dist[s] = 0;
    prev.assign(n, -1);
    priority_queue<Edge> q; // "e < f" <=> "e.weight > f.weight"
    q.push(Edge(-2, s, 0));
    while(q.size()) {
        Edge e = q.top();
        q.pop();
        if (prev[e.dst] != -1) continue;
        prev[e.dst] = e.src;
        for(auto & f : g[e.dst]) {
            if (dist[f.dst] > e.weight+f.weight) {
                dist[f.dst] = e.weight+f.weight;
                q.push(Edge(f.src, f.dst, e.weight+f.weight));
            }
        }
    }
}

int my_stoi(string & s){
    int res = 0;
    rep(i,s.size()) res = res*10 + s[i]-'0';
    return res;
}

int rev(int x){
    stringstream ss;
    ss << x;
    string s = ss.str();
    reverse(all(s));
    return my_stoi(s);
}

int solve_small(int N){
    Graph g(N*10);
    for(int i=1;i<N;i++){
        int d1 = i+1;
        int d2 = rev(i);
        g[i].eb(i,d1,1);
        g[i].eb(i,d2,1);
    }
    vi dist, prev;
    dijk(g,1,dist,prev);
    return dist[N];
}