結果

問題 No.3312 Fire Engine
コンテスト
ユーザー ochiaigawa
提出日時 2025-10-24 22:55:24
言語 C++17
(gcc 13.3.0 + boost 1.87.0)
結果
WA  
実行時間 -
コード長 1,401 bytes
コンパイル時間 2,209 ms
コンパイル使用メモリ 209,140 KB
実行使用メモリ 25,780 KB
最終ジャッジ日時 2025-10-24 22:55:36
合計ジャッジ時間 10,849 ms
ジャッジサーバーID
（参考情報） 		judge2 / judge5
このコードへのチャレンジ
（要ログイン）
ファイルパターン 結果
sample AC * 2
other AC * 8 WA * 34
権限があれば一括ダウンロードができます

ソースコード

diff # 

#include <bits/stdc++.h>
using namespace std;
const int inf = 2000000000;
int main() {
  cin.tie(0); cout.tie(0);
  ios::sync_with_stdio(false);

  int N;
  cin >> N;
  vector<vector<int>> D(N, vector<int>(N));
  for(int i = 0; i < N; i++) {
    for(int j = 0; j < N; j++) {
      cin >> D[i][j];
    }
  }
  for(int k = 0; k < N; k++) {
    for(int i = 0; i < N; i++) {
      for(int j = 0; j < N; j++) {
        D[i][j] = min(D[i][j], D[i][k] + D[k][j]);
      }
    }
  }
  vector<vector<int>> dps(1 << N, vector<int>(N, inf));
  vector<vector<int>> dpt(1 << N, vector<int>(N, inf));
  dps[1][0] = 0;
  dpt[1][0] = 0;
  priority_queue<tuple<int, int, int, int>, vector<tuple<int, int, int, int>>, greater<>> pq;
  pq.push(make_tuple(0, 0, 1, 0));
  while(!pq.empty()) {
    auto [t, s, bit, u] = pq.top();
    pq.pop();
    if(t > dpt[bit][u] && s > dps[bit][u]) {
      continue;
    }
    for(int v = 0; v < N; v++) {
      if(u >> v & 1) {
        continue;
      }
      int nbit = bit | (1 << v);
      int nt = t + D[u][v];
      int ns = s + nt;
      if(dps[nbit][v] <= ns && dpt[nbit][v] <= nt) {
        continue;
      }
      dps[nbit][v] = min(dps[nbit][v], ns);
      dpt[nbit][v] = min(dpt[nbit][v], nt);
      pq.push(make_tuple(nt, ns, nbit, v));
    }
  }
  int ans = inf;
  for(int i = 0; i < N; i++) {
    ans = min(ans, dps.back()[i]);
  }
  cout << ans << '\n';

  return 0;
}
0