#88711 (C++11（廃止可能性あり）) No.134 走れ！サブロー君

• 問題: No.134 走れ！サブロー君
• ユーザー: puru
• 提出日時: 2016-04-29 14:02:53
• 言語: C++11（廃止可能性あり） (gcc 13.3.0)
• 結果: AC
• 実行時間: 61 ms / 5,000 ms
• コード長: 3,521 bytes
• コンパイル時間: 1,305 ms
• コンパイル使用メモリ: 169,452 KB
• 実行使用メモリ: 5,888 KB
• 最終ジャッジ日時: 2024-10-14 17:15:20
• 合計ジャッジ時間: 2,036 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
93
94
95
96
97
98
99
100
101
102
103
104
105
106
107
108
109
110
111
112
113
114
115
116
117
118
119
120
121
122
123
124
125
126
127
128
129
130
131
132
133
134
135
136
137
138
139
140
141
142
143
144
145
146
147
148
149
#include <bits/stdc++.h>
using namespace std;
#define all(c) ((c).begin()), ((c).end())
#define dump(c) cerr << "> " << #c << " = " << (c) << endl;
#define iter(c) __typeof((c).begin())
#define tr(i, c) for (iter(c) i = (c).begin(); i != (c).end(); i++)
#define REP(i, a, b) for (int i = a; i < (int)(b); i++)
#define rep(i, n) REP(i, 0, n)
#define mp make_pair
#define fst first
#define snd second
#define pb push_back
#define debug(fmt, ...) \
        fprintf( stderr, \
                  fmt "\n", \
                  ##__VA_ARGS__ \
        )
typedef unsigned int uint;
typedef long long ll;
typedef unsigned long long ull;
typedef vector<int> vi;
typedef vector<ll> vll;
typedef vector<vll> vvll;
typedef vector<vi> vvi;
typedef vector<double> vd;
typedef vector<vd> vvd;
typedef vector<string> vs;
typedef pair<int, int> pii;
typedef pair<ll, ll> pll;
const int INF = 1 << 29;
const double EPS = 1e-10;
double zero(double d) {
    return d < EPS ? 0.0 : d;
}
template<class T>
bool chmax(T &a, const T &b) {
    if (a < b) {
        a = b;
        return true;
    }
    return false;
}
template<class T>
bool chmin(T &a, const T &b) {
    if (b < a) {
        a = b;
        return true;
    }
    return false;
}
#define UNIQUE(v) v.erase( unique(v.begin(), v.end()), v.end() );
template<typename T1, typename T2>
ostream &operator<<(ostream &os, const pair<T1, T2> &p) {
    return os << '(' << p.first << ',' << p.second << ')';
}
template<typename T>
ostream &operator<<(ostream &os, const vector<T> &a) {
    os << '[';
    rep(i, a.size()) os << (i ? " " : "") << a[i];
    return os << ']';
}
string toString(int i) {
    stringstream ss;
    ss << i;
    return ss.str();
}
const int MOD = 1000000007;
// a^k
ll fpow(ll a, ll k, int M) {
    ll res = 1ll;
    ll x = a;
    while (k != 0) {
        if ((k & 1) == 1)
            res = (res * x) % M;
        x = (x * x) % M;
        k >>= 1;
    }
    return res;
}
struct prepare {
    prepare() {
        cout.setf(ios::fixed, ios::floatfield);
        cout.precision(8);
        ios_base::sync_with_stdio(false);
    }
} _prepare;
int main() {
    int X, Y, N;
    cin >> X >> Y >> N;
    vector<pair<pii, double> > dest(N + 1);
    dest[0] = mp(mp(X, Y), 0);
    rep(i, N) {
        int x, y;
        double w;
        cin >> x >> y >> w;
        dest[i + 1] = mp(mp(x, y), w);
    }
    vector<vector<double> > dp(1 << (N + 1), vector<double>(N + 1, INF));
    dp[1][0] = 0;
    rep(S, 1 << (N + 1)) {
        rep(j, N + 1) {  // from
            REP(i, 1, N + 1) { // to
                if (i == j) continue;
                if (((S >> i) & 1) == 0) {  // not visited
                    double all_w = 0.0;
                    rep(k, N + 1)
                        if (((S >> k) & 1) == 0)   // not visited
                            all_w += dest[k].second;
                    double d = ((all_w + 100) / 120) *
                               (abs(dest[i].first.first - dest[j].first.first) +
                                abs(dest[i].first.second - dest[j].first.second));
                    d += dest[i].second;
                    chmin(dp[S | (1 << i)][i], dp[S][j] + d);
                }
            }
        }
    }
    double ans = INF;
    REP(i, 1, N + 1) {
        double d = (abs(dest[i].first.first - dest[0].first.first) +
                    abs(dest[i].first.second - dest[0].first.second)) * (100.0/120);
        chmin(ans, dp[(1 << (N + 1)) - 1][i] + d);
    }
    cout << ans << endl;
    return 0;
}
 
 
הההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההה
XXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXX