#40450 (C++11) No.134 走れ！サブロー君

• 問題: No.134 走れ！サブロー君
• ユーザー: IL_msta
• 提出日時: 2015-07-31 22:03:06
• 言語: C++11 (gcc 13.3.0)
• 結果: AC
• 実行時間: 19 ms / 5,000 ms
• コード長: 1,817 bytes
• コンパイル時間: 659 ms
• コンパイル使用メモリ: 86,964 KB
• 実行使用メモリ: 5,504 KB
• 最終ジャッジ日時: 2024-10-14 17:14:53
• 合計ジャッジ時間: 1,284 ms
• ジャッジサーバーID （参考情報）: judge4 / judge3

ファイルパターン	結果
other	AC * 15

ソースコード

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
86
87
88
89
90
91
92
#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;
}
 
 
הההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההה
XXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXX