巡回セールスマン問題を面倒くさくした感じ。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; }