結果
問題 | 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 |
ソースコード
// 想定解: 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[最後に行った配達先][既に配達済みのビット] = 時間Tint 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;}