読者です 読者をやめる 読者になる 読者になる

AOJ Problem 0146 : Lupin The 4th

404 Not Found

巡回セールスマン問題を面倒くさくした感じ。50分くらい掛かった。vectorじゃないと配列が取れなかったでござる・・・。

#include <iostream>
#include <vector>
#include <cstdlib>
#include <algorithm>
#include <cmath>
using namespace std;
#define rep(i,n) for(int i=0;i<n;i++)
double w[15],d[15],num[15];
int n;

double weight(int bit){
	double ret = 0;
	for(int i = 0 ; i < n ; i++){
		if( bit & (1<<i) )ret += w[i];
	}
	return 70+20*ret;
}

int main(){
	cin >> n;
	
	vector< vector<double> > dp(1<<15,vector<double>(15,(1<<25))); 
	vector< vector<int> > prevPos(1<<15,vector<int>(15,0)); 
	vector< vector<int> > prevBit(1<<15,vector<int>(15,0));
	
	rep(i,n){
		cin >> num[i] >> d[i] >> w[i];
	}
	
	rep(i,n) dp[(1<<i)][i] = 0.0;
	for(int bit = 1; bit < (1<<n) ; bit++){ // visit info
		for(int i = 0; i < n ; i++){		// prev
			for(int j = 0; j < n ; j++){	// now
				if(bit & (1<<j) )continue;
				int nBit = bit | (1<<j);
				double newDist = dp[bit][i] + fabs(d[i]-d[j]) / ( 2000.0 / weight(bit) );
				
				if(dp[nBit][j] > newDist){
					prevPos[nBit][j] = i;
					prevBit[nBit][j] = bit;
					dp[nBit][j] = newDist;
				}
			}
		}
	}
	vector<int> route;
	int outBit = (1<<n)-1 ,outPos = -1;
	double minCheck = (1<<25);
	
	rep(i,n)if(minCheck > dp[outBit][i]){
		outPos = i;
		minCheck = dp[outBit][i];
	}
	
	route.push_back(outPos);
	while(prevBit[outBit][outPos] != 0){
		int a = prevPos[outBit][outPos] , 
			b = prevBit[outBit][outPos] ;
		outPos = a, outBit = b;
		route.push_back(outPos);
	}
	reverse(route.begin(),route.end());
	
	rep(i,route.size())
		cout << (i?" ":"") << num[route[i]];
	cout << endl;
}