結果

問題 No.3312 Fire Engine
コンテスト
ユーザー Cafe1942
提出日時 2025-10-23 22:33:02
言語 C++17
(gcc 13.3.0 + boost 1.87.0)
結果
WA  
実行時間 -
コード長 2,330 bytes
コンパイル時間 891 ms
コンパイル使用メモリ 115,684 KB
実行使用メモリ 11,904 KB
最終ジャッジ日時 2025-10-23 23:01:05
合計ジャッジ時間 2,935 ms
ジャッジサーバーID
（参考情報） 		judge5 / judge4
このコードへのチャレンジ
（要ログイン）
ファイルパターン 結果
sample AC * 2
other AC * 6 WA * 36
権限があれば一括ダウンロードができます

ソースコード

diff # 

#include <iostream>
#include <iomanip>//小数点出力用
//cout << fixed << setprecision(10) << ans;
#include <cmath>
#include <algorithm>
#include <vector>
#include <queue>
#include <stack>
#include <set>
#include <map>
#include <unordered_map>
using ll = long long;
using namespace std;
#define modPHash (ll)((1LL<<61)-1)
#define modP (ll)998244353
bool chkrng0idx(int pos, int sup) { return (0 <= pos && pos < sup); }
int clk4(int num) { return (num - 2) * (num % 2); }
void yn(bool tf) { cout << (tf ? "Yes\n" : "No\n"); }

int main() {
    cin.tie(nullptr);
    ios::sync_with_stdio(false);
    int N;
    cin >> N;
    //これは嘘解法　dp[S][i] = 訪問済み頂点の集合がSで現在地点iとなるようにできる最速時刻とする。
    int dp[1 << 16][16] = { 0 };
    int dpPre[1 << 16][16] = { 0 };
    int D[16][16];
    for (int i = 0;i < N;i++) {
        for (int j = 0;j < N;j++) {
            cin >> D[i][j];
        }
    }
    for (int k = 1;k < (1 << N);k++) {
        for (int i = 0;i < N;i++) {
            dp[k][i] = 1e9;
            dpPre[k][i] = 1e9;
        }
    }
    dp[1][0] = 0;
    for (int k = 3;k < (1 << N);k += 2) {
        for (int i = 0;i < N;i++) {
            if ((k >> i) & 1) {
                for (int j = 0;j < N;j++) {
                    if (i == j)continue;
                    if ((k >> j) & 1) {
                        if (dp[k][i] > dp[k - (1 << i)][j] + D[j][i]) {
                            dp[k][i] = dp[k - (1 << i)][j] + D[j][i];
                            dpPre[k][i] = j;
                        }
                    }
                }
            }
        }
    }
    int ans = 1e9;
    int id = 1e9;
    for (int i = 1;i < N;i++) {
        if (ans > dp[(1 << N) - 1][i]) {
            ans = dp[(1 << N) - 1][i];
            id = i;
        }
    }
    vector<int>V;
    int bit = 1 << N;
    bit--;
    while (id != 0) {
        V.push_back(id);
        int preid = dpPre[bit][id];
        bit -= (1 << id);
        id = preid;
    }
    reverse(V.begin(), V.end());
    {
        int nowT = 0;
        int nowP = 0;
        int Score = 0;
        vector<int>T(N);
        for (int i = 0;i < N - 1;i++) {
            nowT += D[nowP][V[i]];
            nowP = V[i];
            Score += nowT;
        }
        ans = Score;
    }
    cout << ans;
}
0