結果

問題 No.3158 Collect Stamps
ユーザー twins_fuyu
提出日時 2025-05-23 20:15:53
言語 C++17
(gcc 13.3.0 + boost 1.87.0)
結果
WA  
実行時間 -
コード長 1,455 bytes
コンパイル時間 2,265 ms
コンパイル使用メモリ 215,600 KB
実行使用メモリ 7,848 KB
最終ジャッジ日時 2025-05-23 20:15:57
合計ジャッジ時間 3,621 ms
ジャッジサーバーID
（参考情報） 		judge4 / judge1
このコードへのチャレンジ
（要ログイン）
ファイルパターン 結果
sample AC * 3
other AC * 20 WA * 15
権限があれば一括ダウンロードができます

ソースコード

diff # 

#include <bits/stdc++.h>
using namespace std;

using ll = long long;
using vl = vector<ll>;
using vvl = vector<vl>;

int N,M,K;
vl A;
vvl T;

int main(){
    cin >> N >> M >> K;
    A.resize(K);
    for (int i = 0; i < K; i++){
        cin >> A[i];
        A[i]--; 
    }
    T.resize(N, vl(N));
    for (int i = 0; i < N; i++){
        for (int j = 0; j < N; j++){
            cin >> T[i][j];
        }
    }

    vector<bool> in_A(N, false);
    for (int a : A){
        in_A[a] = true;
    }

    // 最近傍の景品
    vl nearlest(N);
    for (int i=0; i < N; i++){
        ll min = LLONG_MAX;
        for (int a : A){
            if (T[i][a] < min){
                min = T[i][a];
                nearlest[i] = a;
            }
        }
    }

    priority_queue<tuple<ll, int, int, int>, vector<tuple<ll,int,int,int>>,greater<tuple<ll, int, int, int>>> pq;
    for (int i=0; i < N; i++){
        pq.emplace(0,i,1 << i, 1);
    }
    while(!pq.empty()){
        auto [d, pos, bit, cnt] = pq.top();
        pq.pop();
        if (cnt == M){
            if (in_A[pos]){
                cout << d << endl;
                return 0;
            }
            else{
                pq.emplace(d, nearlest[pos], bit | (1 << nearlest[pos]), cnt);
            }
            continue;
        }
        for (int i=0; i < N; i++){
            if (bit & (1 << i)) continue;
            pq.emplace(d + T[pos][i], i, bit | (1 << i), cnt + 1);
        }
    }
}
0