結果

問題 No.3158 Collect Stamps
コンテスト
ユーザー twins_fuyu
提出日時 2025-05-23 20:22:05
言語 C++17
(gcc 13.3.0 + boost 1.87.0)
結果
AC  
実行時間 3 ms / 2,000 ms
コード長 1,522 bytes
コンパイル時間 2,410 ms
コンパイル使用メモリ 216,196 KB
実行使用メモリ 7,844 KB
最終ジャッジ日時 2025-05-23 20:22:28
合計ジャッジ時間 3,618 ms
ジャッジサーバーID
（参考情報） 		judge5 / judge2
このコードへのチャレンジ
（要ログイン）
ファイルパターン 結果
sample AC * 3
other AC * 35
権限があれば一括ダウンロードができます

ソースコード

diff # 

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

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

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 mi = LLONG_MAX;
        for (int a : A){
            if (T[i][a] < mi){
                mi = T[i][a];
                nearlest[i] = a;
            }
        }
    }

    priority_queue<tuple<ll, int, ull, int>, vector<tuple<ll,int,ull,int>>,greater<tuple<ll, int, ull, int>>> pq;
    for (int i=0; i < N; i++){
        pq.emplace(0,i,(1ULL << 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 + T[pos][nearlest[pos]], nearlest[pos], bit | (1ULL << nearlest[pos]), cnt);
            }
            continue;
        }
        for (int i=0; i < N; i++){
            if (bit & (1ULL << i)) continue;
            pq.emplace(d + T[pos][i], i, bit | (1ULL << i), cnt + 1);
        }
    }
}
0