AOJ 0146 - Lupin The 4th

nが100ぐらいまでいくかなー(MLE)
nextは行った集合だけを添え字にすればいいよなー(TLE(推測))
orz

#include<iostream>
#include<algorithm>
#include<vector>

const int MAX_N = 15, INF = 1 << 24;
const double EPS = 1e-10;
int ns[16], d[16], cost[16][16], w[16], weight[1<<MAX_N];
int n, next[1<<MAX_N][16];
double dp[1<<MAX_N][16];

double rec(int S, int v){
	if(dp[S][v] > -EPS){
		return dp[S][v];
	}

	if(S == (1 << n) - 1){
		return 0;
	}

	double min_res = INF;
	for(int i=0;i<n;i++){
		if(!(S >> i & 1)){
			double res = (70.0 + weight[S]) * cost[v][i] / 2000.0 + rec(S | (1 << i), i);
			if(res < min_res + EPS){
				min_res = res;
				next[S][v] = i;
			}
		}
	}

	return dp[S][v] = min_res;
}

int main(){
	std::cin >> n;

	for(int i=0;i<n;i++){
		std::cin >> ns[i] >> d[i] >> w[i];
	}

	for(int i=0;i<(1<<n);i++){
		for(int j=0;j<n;j++){
			if(i >> j & 1){
				weight[i] += w[j];
			}
		}
		weight[i] *= 20;
		std::fill(dp[i], dp[i]+16, -1);
	}

	for(int i=0;i<n;i++){
		cost[n][i] = cost[i][n] = 0;
		for(int j=i+1;j<n;j++){
			cost[i][j] = cost[j][i] = abs(d[i]-d[j]);
		}
	}

	rec(0, n);

	std::vector<int> route;
	int S = 0, u = n;
	while(S != (1 << n) - 1){
		int v = next[S][u];
		S |= (1 << v);
		u = v;
		route.push_back(ns[u]);
	}

	std::cout << route[0];
	for(int i=1;i<route.size();i++){
		std::cout << " " << route[i];
	}
	std::cout << std::endl;
}