No.134 走れ!サブロー君 - yukicoder
- bit DP の問題。最初 weigth の値も込みの dp[bit][weight] みたいな DP かと思ったが bit だけで weight が計算できることに気づけた。
- 問題文の重みが double だってことに気づかずに int w; に cin>>w; してしまって WA してしまった。
- bit DP はまだまだ実装練習が必要そう。
class GoSabrou {
public:
void solve(void) {
int x0,y0;
cin>>x0>>y0;
int N;
cin>>N;
vector<tuple<int,int,double>> dest;
dest.emplace_back(x0,y0,0);
REP(i,N)
{
int x,y;
double w;
cin>>x>>y>>w;
dest.emplace_back(x,y,w);
}
++N;
const int inf = (1<<30);
vector<vector<int>> dist(N,vector<int>(N,inf));
REP(i,N)
FOR(j,i+1,N)
{
const auto &p = dest[i];
const auto &q = dest[j];
int d = abs(get<0>(p)-get<0>(q)) + abs(get<1>(p)-get<1>(q));
dist[i][j] = dist[j][i] = d;
}
vector<double> weights(1<<N, 0);
REP(unvis, (1<<N))
{
double w = 0;
REP(i,N) if ( unvis & (1<<i) )
w += get<2>(dest[i]);
weights[unvis] = w;
}
vector<vector<double>> dp(1<<N, vector<double>(N,inf));
dp[(1<<N)-1][0] = 0;
for (int unvis = (1<<N)-2; unvis >= 0; --unvis)
{
REP(v,N)
{
REP(u,N)
{
if ( unvis & (1<<u) )
continue;
double cost = (weights[unvis]+100.0)/120.0 * dist[u][v] + get<2>(dest[v]);
dp[unvis][v] = min(dp[unvis][v], dp[unvis|(1<<u)][u] + cost);
}
}
}
cout<<setprecision(20)<<dp[0][0]<<endl;
}
};