読者です 読者をやめる 読者になる 読者になる

Facebook Hacker Cup 2017 Round 1 - Manic Moving

問題

Manic Moving | Facebook Hacker Cup 2017 Round 1

考察

まずは、各都市間の最小移動コストを出します。
N=100と小さいので、ワーシャルフロイドで簡単に求まります。

制約として、荷物は最大2組まで積み込めますが、積み込み・荷降ろしはそれぞれ順番に行われる必要があります。
ややこしく見えますが、積み込み・荷降ろしは独立していることを活かすと、次のようなDPが考えられます。

dp[i][j][k] := i個目まで荷降ろしが完了し、現在j組の荷物が乗っていて、k番目の都市にいる時の最小コスト

状態遷移としては、まず「積み込み」を考えます。
積み込みの時は荷降ろしは考えないので、iは変更されません。 現在いる都市(k)と、次に積みこむ都市(lp)はjが決まっていればすぐわかるので、jが増える方向に更新をします。

min: dp[i][j+1][lp] = dp[i][j][k] + dist[k][lp]

1個、2個の場合の積み込みを計算し終わったら、荷降ろしに移ります。
これはjを減らし、iを1増やす更新です。
同じ都市で2個降ろせる場合もありますが、そのような場合でも1つずつ考慮することで簡単になります(移動コストが0なので上手く行く)。
lpは次に荷降ろしをするべき都市なので、iを見ると簡単に求まります。

min: dp[i+1][j-1][lp] = dp[i][j][k] + dist[k][lp]

このようにDP表を更新すると、最後に荷降ろしする都市でのコストが答えになります。

コード

ll solve() {
    int N, M, K;
    cin >> N >> M >> K;

    const ll INF = 1ll << 60;
    vvll dist(N, vll(N, INF));
    rep(i, N)dist[i][i] = 0;

    rep(i, M) {
        int a, b, g;
        cin >> a >> b >> g;
        --a, --b;
        chmin(dist[a][b], (ll)g);
        chmin(dist[b][a], (ll)g);
    }

    rep(k, N) {
        rep(i, N) {
            rep(j, N) {
                chmin(dist[i][j], dist[i][k] + dist[k][j]);
            }
        }
    }

    vector<pii> fam(K);
    rep(i, K) {
        int s, d;
        cin >> s >> d;
        --s, --d;
        fam[i] = mp(s, d);
    }

    vector<vvll> dp(K+1, vvll(3, vll(N, INF)));
    dp[0][0][0] = 0;

    rep(i, K) {
        // load
        rep(j, 3-1) {
            int next = i + j;
            if(next >= K)
                continue;
            int lp = fam[next].first;
            rep(k, N) {
                if(dp[i][j][k] >= INF)
                    continue;
                chmin(dp[i][j+1][lp], dp[i][j][k] + dist[k][lp]);
            }
        }

        // unload
        REP(j, 1, 3) {
            int next = i;
            if(next >= K)
                continue;
            int lp = fam[next].second;
            rep(k, N) {
                if(dp[i][j][k] >= INF)
                    continue;
                chmin(dp[i+1][j-1][lp], dp[i][j][k] + dist[k][lp]);
            }
        }
    }

    ll ans = dp[K][0][fam[K-1].second];
    if(ans >= INF)
        return -1;
    else
        return ans;
}


int main() {
    int T;
    cin >> T;
    rep(__t, T) {
        cout << "Case #" << __t + 1 << ": ";
        cout << solve() << endl;
    }

    return 0;
}

感想

普通に引越し屋さんとかで使えそうです。