AOJ 0146 - Lupin The 4th
問題文 : ルパン四世
解法 :
まず, bitDPで最短時間を求める.
その後に, 最短時間を達成する訪問の仕方を出発するノードから確かめていく.
出発するノードは, dp[S | S_n = 1, else S_i = 0][n]の中で最も小さいものとなる.
誤差に注意して計算していくこと.
コード :
#include <cstdio> #include <algorithm> #include <cmath> #define EPS (0.0001) using namespace std; typedef struct { int no; int dist; int money; } Store; Store data[16]; double dp[1 << 16][16]; int n; double mT; void print(int S, int v, double sum) { printf("%d%c", data[v].no, S == (1 << n) - 1 ? '\n' : ' '); if (S == (1 << n) - 1) return; int sumMoney = 0; for (int i = 0; i < n; i++){ if ((S >> i) & 1) sumMoney += data[i].money; } int nxt; double nowTime; for (int i = 0; i < n; i++){ int dx = abs(data[v].dist - data[i].dist); double nv = 2000.0 / (70 + 20 * sumMoney); nowTime = dx / nv; if (!((S >> i) & 1) && fabs(sum + nowTime + dp[S | (1 << i)][i] - mT) <= EPS){ nxt = i; break; } } print(S | (1 << nxt), nxt, sum + nowTime); } double getTime(int S, int v) { int ans[16]; if (~v && dp[S][v] >= 0){ return (dp[S][v]); } if (S == (1 << n) - 1){ return (dp[S][v] = 0); } int sumMoney = 0; for (int i = 0; i < n; i++){ if ((S >> i) & 1) sumMoney += data[i].money; } int minNode; double minTime = -1; for (int i = 0; i < n; i++){ if (!((S >> i) & 1)){ int dx = abs((~v ? data[v].dist : 0) - data[i].dist); double nv = 2000.0 / (70 + 20 * sumMoney); double nowTime = (~v ? dx / nv : 0) + getTime(S | (1 << i), i); if (minTime < 0) minTime = nowTime; else minTime = min(minTime, nowTime); if (minTime == nowTime){ minNode = i; } } } if (~v){ return (dp[S][v] = minTime); } else { mT = minTime; print(1 << minNode, minNode, 0); return (minTime); } } int main() { int route[16]; scanf("%d", &n); for (int i = 0; i < n; i++){ scanf("%d %d %d", &data[i].no, &data[i].dist, &data[i].money); } for (int i = 0; i < 1 << 16; i++){ for (int j = 0; j < 16; j++){ dp[i][j] = -1; } } getTime(0, -1); return (0); }