Lilliput Steps

小さな一歩から着実に. 数学やプログラミングのことを書きます.

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