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; }