AOJ Lupin The 4th

Lupin The 4th | Aizu Online Judge

巡回セールスマン問題。経路復元が必要。 経路復元は、それ用に配列をもう一つ用意しておいて、最短の移動順序を記録しておく。

double dp[100000][20];
int pos[100000][20];
int n;
int kura[20], d[20], sen[20];

double solve(int S, int v, int weight) {
    if (S == ((1 << n) - 1)) return dp[S][v] = 0;
    if (dp[S][v] >= 0) return dp[S][v];

    double res = 1000*1000*1000;
    for (int i = 0; i < n; i++) {
        if (!(S & (1 << i))) {
            double td = abs(d[i]-d[v]);
            double ts = 2000.0/(double)(70+weight);
            double tres = solve(S | (1 << i), i, sen[i]*20 + weight) + td/ts;
            if (res > tres) {
                res = tres;
                pos[S][v] = i;
            }
        }
    }
    return dp[S][v] = res;
}

int main() {
    cin >> n;
    for (int i = 0; i < 100000; i++) fill(dp[i], dp[i]+20, -1);
    for (int i = 0; i < n; i++) {
        cin >> kura[i] >> d[i] >> sen[i];
    }
    d[n] = 0;
    solve(0, n, 0);
    int S = 0, cur = n;
    vector<int> r;
    for (int i = 0; i < n; i++) {
        int next = pos[S][cur];
        r.push_back(next);
        S = (S | (1 << next));
        cur = next;
    }
    for (int i = 0; i < n-1; i++) cout << kura[r[i]] << ' ';
    cout << kura[r[n-1]] << endl;
    return 0;
}