結果

問題 No.134 走れ！サブロー君
ユーザー IL_mstaIL_msta
提出日時 2015-07-31 22:03:06
言語 C++11
(gcc 11.4.0)
結果
AC  
実行時間 16 ms / 5,000 ms
コード長 1,817 bytes
コンパイル時間 1,039 ms
コンパイル使用メモリ 86,816 KB
実行使用メモリ 5,376 KB
最終ジャッジ日時 2024-04-22 18:03:44
合計ジャッジ時間 1,403 ms
ジャッジサーバーID
（参考情報） 		judge4 / judge3
このコードへのチャレンジ
（要ログイン）

テストケース

テストケース表示
入力 結果 実行時間
実行使用メモリ
testcase_00 AC 1 ms
5,248 KB
testcase_01 AC 2 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 5 ms
5,376 KB
testcase_07 AC 8 ms
5,376 KB
testcase_08 AC 16 ms
5,376 KB
testcase_09 AC 16 ms
5,376 KB
testcase_10 AC 2 ms
5,376 KB
testcase_11 AC 1 ms
5,376 KB
testcase_12 AC 1 ms
5,376 KB
testcase_13 AC 1 ms
5,376 KB
testcase_14 AC 2 ms
5,376 KB
権限があれば一括ダウンロードができます

ソースコード

diff # 

#define _USE_MATH_DEFINES
 
#include <iostream>
#include <iomanip>
#include <sstream>
 
#include <algorithm>
#include <cmath>
 
#include <string>
//#include <array>
#include <list>
#include <queue>
#include <vector>
#include <complex>
#include <set>
#include <map>
 
/////////
#define REP(i, x, n) for(int i = x; i < n; i++)
#define rep(i,n) REP(i,0,n)
#define P(p) cout<<(p)<<endl;
 
#define PII pair<int,int>
/////////
typedef long long LL;
typedef long double LD;
/////////
using namespace::std;
/////////

LD dp[1<<13][14];
int main(void){
    std::cin.tie(0); 
    std::ios::sync_with_stdio(false);
    std::cout << std::fixed;//
    cout << setprecision(16);//
	

	int posX[14],posY[14],N;
	double W[14];
	cin>>posX[0]>>posY[0];
	cin>>N;
	rep(i,N){
		cin>>posX[i+1]>>posY[i+1]>>W[i+1];
	}
	LD mas,temp;
	rep(i,1<<N)rep(j,N+1)dp[i][j] = -1;

	dp[0][0] = 0;
	for(int i=0;i<(1<<N);++i){//運んだ荷物bit
		for(int j=0;j<N;++j){//選択　届ける荷物
			if( !( i & (1<<j) ) ){
				for(int k=0;k<=N;++k){//現在位置
					if( dp[i][k] >= 0 ){
						mas = 0;
						rep(m,N){
							if( !(i & (1<<m)) ){
								mas += W[m+1];
							}
						}
						if( dp[(i|(1<<j))][j+1] > 0){
							temp = dp[i][k] + ( abs(posX[j+1] - posX[k]) + abs( posY[j+1] - posY[k]) ) * (mas+100.0)/120;
							if( 0 > dp[i|(1<<j)][j+1] || dp[i|(1<<j)][j+1] > temp ){
								dp[ i | (1<<j)][j+1] = temp;
							}
							
						}else{
							dp[ i | (1<<j)][j+1] = dp[i][k] + 
							( abs(posX[j+1] - posX[k])+abs(posY[j+1] - posY[k]) )*(mas+100.0)/120 ;
						}
					}
				}
			}
		}
	}
	LD ans = -1;
	rep(i,N){
		temp = dp[(1<<N)-1][i+1] + ( abs(posX[i+1] - posX[0]) + abs(posY[i+1]-posY[0]) )*100.0/120;
		if( ans < 0){
			ans = temp;
		}else{
			ans = min(ans,temp);
		}
	}
	rep(i,N){
		ans += W[i+1];
	}

	P(ans);
	return 0;
}
0