問題概要

3 次元空間内に $N$ 個の都市、都市 1 から都市 N がある。

座標 $(a, b, c)$ の都市から $(p, q, r)$ の都市に移動する際には $|p−a|+|q−b|+\max(0,r−c)$ のコストがかかる。

都市 1 からスタートし、全ての都市を 1 度以上巡って都市 1 に戻るまでの最小コストを求めよ。

制約

$2 \le N \le 17$

考えたこと

最初、 $N \le 17$ という制約を見逃して、こんなの解けるのかーー！？となってた。そして $N \le 17$ という制約を見つけてからは「ただの TSP に対する bit DP じゃん」と思ってそれで解いてしまった。

ただ今回は「すべての都市をちょうど 1 回辿って」ではなく「1 回以上辿って」という設定なので注意が必要だった。

三角不等式とは、任意の 3 頂点 A, B, C に対して

「辺 (AC) の長さ <= 辺 (AB) の長さ + 辺 (BC) の長さ」

が成立することをいう。しかしこれがなかったら、「同じ頂点を一度以上巡る解」が最適になるとは限らない。その場合はこの問題を解くためには

一度 Warshall-Floyd 法などによって、各頂点間の最短路をあらかじめ求めてから
通常の TSP (各頂点一度だけ) を解く

という風にしなければならなかった。今回は三角不等式が成立しているので、通常の TSP をすれば問題ない状態になっていた。

#include <bits/stdc++.h>
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 long long INF = 1LL<<60;
int main() {
    int N;
    cin >> N;
    vector<long long> X(N), Y(N), Z(N);
    for (int i = 0; i < N; ++i) cin >> X[i] >> Y[i] >> Z[i];

    auto dis = [&](int v, int nv) {
        long long add = abs(X[v] - X[nv]) + abs(Y[v] - Y[nv]) + max(0LL, Z[nv] - Z[v]);
        return add;  
    };
    vector<vector<long long>> dp(1<<N, vector<long long>(N+1, INF));
    dp[1][0] = 0;
    for (int bit = 0; bit < (1<<N); ++bit) {
        for (int v = 0; v < N; ++v) {
            if (!(bit & (1<<v))) continue;
            for (int nv = 0; nv < N; ++nv) {
                if (bit & (1<<nv)) continue;
                int nbit = bit | (1<<nv);
                chmin(dp[nbit][nv], dp[bit][v] + dis(v, nv));
            }
        }
    }
    long long res = INF;
    for (int v = 0; v < N; ++v) {
        chmin(res, dp[(1<<N)-1][v] + dis(v, 0));
    }
    cout << res << endl;
}

けんちょんの競プロ精進記録

競プロの精進記録や小ネタを書いていきます

AtCoder ABC 180 E - Traveling Salesman among Aerial Cities (水色, 500 点)

問題概要

制約

考えたこと