hogecoder

tsutaj 競技プログラミングの記録

Google Code Jam Round 1B 2017 C: Pony Express

想定解法と違う方法で解いたので一応メモ。

問題概要

街が  N  (2 \le N \le 100) つあり、街  i j を結ぶ道路の長さは  D_{ij} (km) (-1 \le D_{ij} \le 10^{9}, ただし  -1 の時は道路がないことを表す) である。

それぞれの街には馬がおり、街  i にいる馬は時速  s_{i} (km/h)  (1 \le s_{i} \le 10^{3}) で移動することができ、最大で  e_{i} (km)  (1 \le e_{i} \le 10^{9}) 移動できる。街と街の移動には馬を利用する (必要ならば途中の街で馬を乗り継ぐこともできる)。このとき、以下のクエリを  Q (1 \le Q \le 100) 処理せよ。

  •  U から  V に向けて、上記の制約を満たした乗り継ぎをしながら馬に乗って行くことを考えたとき、かかる時間の最小値を求めよ。

解説

拡張ダイクストラで求めることができます。

rec[i][j][k] := 街 i を出発時点で、今乗っている馬 j が距離 k を走った時にかかる累計時間の最小値 となるような配列を作ります。この配列を真面目に取ろうとしても  10^{2} \times 10^{2} \times 10^{9} のサイズの配列を取らなければならないので無理ですが、実際はそのほとんどが使われることが無いため、使うところだけ利用できるように map を利用して作ることにします。

 x から  y に行く際には、馬の走れる距離が十分にあると仮定すると以下の  2 つの遷移が考えられます。

  •  y に着いた後も、今乗っている馬に乗り続ける
  •  y に着いたら、街  y にいる馬に乗り換える

別の馬に乗り換えた場合、走行距離の情報がリセットされることに注意して遷移すれば良いです。制約を満たさない動き (たとえば、馬の走行距離の限界を超えるなど) をしないようにすることも重要です。

ソースコード

struct Elem {
    int city, horse, dist;
    double cost;
    Elem(int a, int b, int c, double d) : city(a), horse(b), dist(c), cost(d) {}
};

bool operator<(const Elem &a, const Elem &b) {
    return a.cost > b.cost;
}

int e[110], s[110];
int mat[110][110];
signed main() {
    int t; cin >> t;
    repq(cs,1,t) {
        int N, Q; cin >> N >> Q;
        rep(i,0,N) cin >> e[i] >> s[i];
        rep(i,0,N) rep(j,0,N) cin >> mat[i][j];
        printf("Case #%lld:", cs);
        rep(i,0,Q) {
            // city, horse, dist
            map<int, map<int, map<int, double> > > rec;
            int u, v; cin >> u >> v;
            double ans = DBL_MAX;
            u--; v--;
            priority_queue<Elem> q;
            q.push(Elem(u, u, 0, 0.0));
            while(!q.empty()) {
                Elem pick = q.top(); q.pop();
                int from = pick.city, d = pick.dist, usg = pick.horse;
                if(from == v) {
                    ans = min(ans, pick.cost);
                    break;
                }
                rep(to,0,N) {
                    if(mat[from][to] == -1) continue;
                    if(d + mat[from][to] > e[usg]) continue;
                    int nd = d + mat[from][to];
                    double c = (double)mat[from][to] / s[usg];
                    if(!rec[to][usg].count(nd) || rec[to][usg][nd] > rec[from][usg][d] + c) {
                        rec[to][usg][nd] = rec[from][usg][d] + c;
                        q.push(Elem(to, usg, nd, rec[to][usg][nd]));
                    }
                    if(!rec[to][to].count(0) || rec[to][to][0] > rec[from][usg][d] + c) {
                        rec[to][to][0] = rec[from][usg][d] + c;
                        q.push(Elem(to, to, 0.0, rec[to][to][0]));
                    }
                }
            }
            printf(" %.12lf", ans);
        }
        cout << endl;
    }
    return 0;
}

実はワーシャルフロイドを 2 回やる想定解法をまだ読んでいない・・・ (読もう)