結果

問題 No.134 走れ！サブロー君
コンテスト
ユーザー tac
提出日時 2019-04-27 16:34:57
言語 C++14
(gcc 13.3.0 + boost 1.87.0)
結果
AC  
実行時間 6 ms / 5,000 ms
コード長 1,907 bytes
コンパイル時間 1,210 ms
コンパイル使用メモリ 103,360 KB
実行使用メモリ 5,248 KB
最終ジャッジ日時 2024-11-28 08:57:26
合計ジャッジ時間 1,914 ms
ジャッジサーバーID
（参考情報） 		judge2 / judge4
このコードへのチャレンジ
（要ログイン）
ファイルパターン 結果
other AC * 15
権限があれば一括ダウンロードができます

ソースコード

diff # 

#include<iostream>
#include<vector>
#include<algorithm>
#include<queue>
#include<map>
#include<stack>
#include<cmath>
#include<iomanip>
#include<set>
#include<numeric>
#include<sstream>
#include<random>
#include<cassert>
#include<list>
using namespace std;
typedef long long ll;
#define rep(i, n) for (int i = 0; i < n; ++i)
#define rrep(i, st, n) for (int i = st; i < n; ++i)
using pii = pair<int, int>;
const int inf = 1e9 + 7;
int dy[] = {1, 1, 0, -1, -1, 0};
int dx[] = {1, 0, -1, -1, 0, 1};
#define ceil(a, b) a / b + !!(a % b)
#define chmax(a, b) a = max(a, b)
#define chmin(a, b) a = min(a, b)

double dp[1 << 16][16];
double x[17], y[17], w[17];
int x0, y00;
void init(int n, double sum) {
    rep(i, (1 << n)) rep(j, n) dp[i][j] = inf;
    rep(i, n) dp[0][i] = 0;
    rep(i, n) {
        double tmp = abs(x[i] - x0) + abs(y[i] - y00);
        tmp *= (sum + 100) / 120;
        dp[1 << i][i] = tmp + w[i];
    }
}
int main() {
    cin >> x0 >> y00;
    int n;
    cin >> n;
    
    double sum = 0;
    rep(i, n) {cin >> x[i] >> y[i] >> w[i]; sum += w[i];}
    init(n, sum);
    rep(i, (1 << n)) {
        double t = sum;
        rep(j, n) {
            if (i & (1 << j)) {
                t -= w[j];
            }
        }
        t = (t + 100) / 120;
        rep(j, n) {
            if (!(i & (1 << j))) {
                rep(k, n) {
                    if (i & (1 << k)) {
                        double tmp = t * (abs(x[k] - x[j]) + abs(y[k] - y[j]));
                        
                        chmin(dp[i | 1 << j][j], dp[i][k] + tmp + w[j]);
                    }
                }
            }
        }
    }
    //rep(i, (1 << n)) {rep(j, n) cout << dp[i][j] << " "; cout << endl;}
    double ans = inf;
    
    rep(i, n) {
        chmin(ans, dp[(1 << n) - 1][i] + (abs(x[i] - x0) + abs(y[i] - y00)) * 100.0 / 120);
    }
    cout << fixed << setprecision(10) << ans << endl;
}
0