結果
問題 |
No.134 走れ!サブロー君
|
ユーザー |
|
提出日時 | 2025-10-04 22:44:59 |
言語 | D (dmd 2.109.1) |
結果 |
AC
|
実行時間 | 23 ms / 5,000 ms |
コード長 | 1,693 bytes |
コンパイル時間 | 6,153 ms |
コンパイル使用メモリ | 209,588 KB |
実行使用メモリ | 9,224 KB |
最終ジャッジ日時 | 2025-10-04 22:45:06 |
合計ジャッジ時間 | 7,307 ms |
ジャッジサーバーID (参考情報) |
judge1 / judge4 |
(要ログイン)
ファイルパターン | 結果 |
---|---|
other | AC * 15 |
ソースコード
module main; // https://mmxsrup.hatenablog.com/entry/2016/10/21/155306 より // 2次元グリッド、巡回セールスマン問題、bitDP import std; // aとbを比較してbの方が小さいならばaの値をbに更新する void chMin(T)(ref T a, in T b) { if (a > b) a = b; } void main() { // 入力 int[] X = [0], Y = [0]; readln.chomp.formattedRead("%d %d", X[0], Y[0]); int N = readln.chomp.to!int; X.length = N + 1; Y.length = N + 1; auto W = new double[](N + 1); W[0] = 0.0; foreach (i; 1 .. N + 1) readln.chomp.formattedRead("%d %d %f", X[i], Y[i], W[i]); // 答えの計算 // mask集合の時の荷物の重さ auto weight = new double[](1 << (N + 1)); auto dist = new int[][](N + 1, N + 1); foreach (i; 0 .. N + 1) foreach (j; 0 .. N + 1) dist[i][j] = abs(X[i] - X[j]) + abs(Y[i] - Y[j]); // 前計算 foreach (mask; 0 .. 1 << (N + 1)) { double tmp = 0.0; foreach (i; 0 .. N + 1) { if ((mask & (1 << i)) == 0) tmp += W[i]; weight[mask] = tmp; } } immutable INF = 10 ^^ 9; // mask集合を巡って、iにいるときの最小コスト auto dp = new double[][](1 << (N + 1), N + 1); foreach (ref row; dp) row[] = INF; dp[0][0] = 0; foreach (mask; 0 .. 1 << (N + 1)) { foreach (i; 0 .. N + 1) { // 現在地点 foreach (p; 0 .. N + 1) { // 次の地点 if ((mask & (1 << p)) == 0) { // pをまだ訪れていない //mask集合を訪れた後に、iからpに向かうときにかかるコスト double cost = dist[i][p] * (weight[mask] + 100.0) / 120.0; chMin(dp[mask | (1 << p)][p], dp[mask][i] + cost); } } } } // 答えの出力 writefln("%.12f", dp[(1 << (N + 1)) - 1][0] + W.sum); }