結果

問題 No.134 走れ！サブロー君
コンテスト
ユーザー evima
提出日時 2015-01-22 23:37:49
言語 C++11（廃止可能性あり）
(gcc 13.3.0)
結果
AC  
実行時間 10 ms / 5,000 ms
コード長 1,252 bytes
コンパイル時間 1,171 ms
コンパイル使用メモリ 159,116 KB
実行使用メモリ 5,504 KB
最終ジャッジ日時 2024-10-14 17:10:42
合計ジャッジ時間 1,784 ms
ジャッジサーバーID
（参考情報） 		judge4 / judge3
このコードへのチャレンジ
（要ログイン）
ファイルパターン 結果
other AC * 15
権限があれば一括ダウンロードができます

ソースコード

diff # 

// Enjoy your stay.

#include <bits/stdc++.h>

#define EPS 1e-9
#define INF 1070000000LL
#define MOD 1000000007LL
#define all(x) (x).begin(),(x).end()
#define fir first
#define foreach(it,X) for(auto it=(X).begin();it!=(X).end();it++)
#define ite iterator
#define mp make_pair
#define mt make_tuple
#define rep(i,n) rep2(i,0,n)
#define rep2(i,m,n) for(int i=m;i<(n);i++)
#define pb push_back
#define sec second
#define sz(x) ((int)(x).size())

using namespace std;

typedef istringstream iss;
typedef long long ll;
typedef pair<ll,ll> pi;
typedef stringstream sst;
typedef vector<ll> vi;

int n;
int x[14],y[14];
double w[14];
double dp[14][1<<14];

int d(int i,int j){
	return abs(x[i]-x[j])+abs(y[i]-y[j]);
}

double f(int cur,int mask){
	double& res = dp[cur][mask];
	if(res != -INF) return res;
	res = INF;
	double W = 0;
	rep(i,n)if(mask>>i&1) W += w[i];
	double T = (W + 100) / 120.;
	if(mask == 0){
		res = T * d(cur,0);
	}else{
		rep2(i,1,n)if(mask>>i&1){
			res = min(res, w[i]+T*d(cur,i) + f(i,mask^1<<i));
		}
	}
	return res;
}

int main(){
	cin.tie(0);
	ios_base::sync_with_stdio(0);
	
	cin>>x[0]>>y[0]>>n;
	n++;
	rep2(i,1,n){
		cin>>x[i]>>y[i]>>w[i];
	}
	rep(i,n)rep(j,1<<n)dp[i][j]=-INF;
	cout<<setprecision(16)<<f(0,(1<<n) - 2)<<endl;
}
0