結果

問題 No.134 走れ!サブロー君
ユーザー なお
提出日時 2015-01-12 23:14:17
言語 C++11
(gcc 13.3.0)
結果
AC  
実行時間 6 ms / 5,000 ms
コード長 2,005 bytes
コンパイル時間 1,494 ms
コンパイル使用メモリ 162,020 KB
実行使用メモリ 5,248 KB
最終ジャッジ日時 2024-10-14 17:10:40
合計ジャッジ時間 2,009 ms
ジャッジサーバーID
(参考情報)
judge2 / judge4
このコードへのチャレンジ
(要ログイン)
ファイルパターン 結果
other AC * 15
権限があれば一括ダウンロードができます

ソースコード

diff #
プレゼンテーションモードにする

// : bitDP
#include <bits/stdc++.h>
using namespace std;
typedef long long ll;
template<typename _T> void rc(_T v,_T mn,_T mx){if(v<mn||mx<v){cerr<<"error"<<endl;exit(1);}}
#define REP(i, n) for(int(i)=0;(i)<(n);++(i))
#define FOR(i, f, t) for(int(i)=(f);(i)<(t);(++i))
const int MINN = 1, MAXN = 13;
const int MINXY = 0, MAXXY = 1000;
const double MINW = 1, MAXW = 100;
const double EPS = 1e-7;
int N;
int Xbase, Ybase;
int X[MAXN+1], Y[MAXN+1];
double W[MAXN+1];
int dist[MAXN+1][MAXN+1];
const double INF = 1e9;
double Wsum[1<<MAXN];
double dp[MAXN][1<<MAXN]; // dp[][] = T
int main(){
cin >> Xbase >> Ybase;
cin >> N; rc(N, MINN, MAXN);
REP(i,N){
cin >> X[i] >> Y[i] >> W[i];
rc(X[i], MINXY, MAXXY); rc(Y[i], MINXY, MAXXY); rc(W[i], MINW, MAXW);
}
//
Wsum[0] = 0;
REP(i,N){
REP(j,(1<<i)) Wsum[j+(1<<i)] = Wsum[j]+W[i];
}
//
REP(i,N) REP(j,N){
dist[i][j] = abs(X[i]-X[j]) + abs(Y[i]-Y[j]);
}
REP(i,N) REP(j,1<<N) dp[i][j] = INF;
unsigned int fullbit = (1<<N)-1;
//
REP(i,N){
int d = abs(X[i]-Xbase) + abs(Y[i]-Ybase);
dp[i][1<<i] = d * (Wsum[fullbit] + 100) / 120.0 + W[i];
}
FOR(i,1,(1<<N)) REP(j,N){
if((i & (1<<j)) == 0) continue;
REP(k,N){ //
if(i & (1<<k)) continue;
int d = abs(X[k]-X[j]) + abs(Y[k]-Y[j]);
double t = dp[j][i] + d * (Wsum[fullbit]-Wsum[i] + 100) / 120.0 + W[k];
dp[k][i|(1<<k)] = min(dp[k][i|(1<<k)], t);
}
}
//
double mint = INF;
REP(i,N){
int d = abs(X[i]-Xbase) + abs(Y[i]-Ybase);
mint = min(mint, dp[i][fullbit] + d * (0 + 100) / 120.0);
}
cout << fixed << setprecision(9) << mint << endl;
}
הההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההה
XXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXX
1