結果

問題 No.134 走れ！サブロー君
ユーザー koyumeishikoyumeishi
提出日時 2015-01-30 20:54:45
言語 C++11
(gcc 11.4.0)
結果
AC  
実行時間 10 ms / 5,000 ms
コード長 1,435 bytes
コンパイル時間 1,001 ms
コンパイル使用メモリ 82,764 KB
実行使用メモリ 5,888 KB
最終ジャッジ日時 2024-04-22 18:01:29
合計ジャッジ時間 1,575 ms
ジャッジサーバーID
（参考情報） 		judge2 / judge3
このコードへのチャレンジ
（要ログイン）

テストケース

テストケース表示
入力 結果 実行時間
実行使用メモリ
testcase_00 AC 2 ms
5,248 KB
testcase_01 AC 1 ms
5,376 KB
testcase_02 AC 2 ms
5,376 KB
testcase_03 AC 2 ms
5,376 KB
testcase_04 AC 2 ms
5,376 KB
testcase_05 AC 3 ms
5,376 KB
testcase_06 AC 3 ms
5,376 KB
testcase_07 AC 6 ms
5,376 KB
testcase_08 AC 10 ms
5,760 KB
testcase_09 AC 10 ms
5,888 KB
testcase_10 AC 2 ms
5,376 KB
testcase_11 AC 2 ms
5,376 KB
testcase_12 AC 2 ms
5,376 KB
testcase_13 AC 2 ms
5,376 KB
testcase_14 AC 1 ms
5,376 KB
権限があれば一括ダウンロードができます

ソースコード

diff # 

#include <iostream>
#include <vector>
#include <cstdio>
#include <sstream>
#include <map>
#include <string>
#include <algorithm>
#include <queue>
#include <cmath>
#include <set>
using namespace std;

double weight(vector<double> &w, int s){
	double ret = 0;
	for(int i=0; i<w.size(); i++){
		if((s>>i) & 1){
			ret += w[i];
		}
	}
	return ret;
}

double dfs(vector<vector<double>> &memo, vector<int> &x, vector<int> &y, vector<double> &w, int s, int pos){
	if(memo[s][pos] >= 0){
		return memo[s][pos];
	}

	int n = x.size()-1;
	double ret = 1e9;
	double w_ = weight(w, s|(1<<pos));

	for(int i=0; i<n; i++){
		if((s>>i) & 1) continue;
		if(i==pos) continue;
		int dist = abs(x[pos] - x[i]) + abs(y[pos] - y[i]);
		double t = (w_ + 100.0)/120.0 * dist + w[pos];
		double tmp = t + dfs(memo,x,y,w, s|(1<<pos), i);
		ret = min(ret, tmp);
	}

	memo[s][pos] = ret;
	return ret;

}

int main(){
	int x_,y_;
	cin >> x_ >> y_;
	int n;
	cin >> n;
	vector<int> x(n);
	vector<int> y(n);
	vector<double> w(n);

	for(int i=0; i<n; i++){
		cin >> x[i] >> y[i] >> w[i];
	}
	x.push_back(x_);
	y.push_back(y_);
	w.push_back(0);

	vector<vector<double>> dp(1<<(n+1), vector<double>(n+1, -1.0));
	double sum = weight(w, (1<<n)- 1 );
	for(int i=0; i<n; i++){
		int dist = abs(x_ - x[i]) + abs(y_ - y[i]);
		dp[ ((1<<(n+1))-1) ^ (1<<i) ][i] = (sum + 100.0)/120.0 * dist + w[i];
	}

	double ans = dfs(dp, x,y,w, 0, n);
	printf("%.11f\n", ans);
	return 0;
}
0