結果

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

ソースコード

diff # 

#include <bits/stdc++.h>
#include <atcoder/all>
using namespace std;
typedef long long ll;
const int INF = 1<<30;
const ll INFLL = 1LL<<60;
const ll MOD = 998244353;
const double INFD = 1.0E18;
const int dx[4] = {1, 0, -1, 0};
const int dy[4] = {0, -1, 0, 1};
//const int dx[8] = {1, 1, 0, -1, -1, -1, 0, 1};
//const int dy[8] = {0, 1, 1, 1, 0, -1, -1, -1};
using Pair = pair<ll, ll>;
using Graph = vector<vector<pair<int, int>>>;
using mint = atcoder::modint1000000007;


int main(){
    ios::sync_with_stdio(false);
    cin.tie(nullptr);
    cout << fixed << setprecision(15);
    int n, m, k; cin >> n >> m >> k;
    vector<int> recieve(k);//景品がある場所
    for (int i = 0; i < k; i++){
        cin >> recieve[i];
        recieve[i]--;
    }
    
    
    vector<vector<int>> dist(n, vector<int>(n));
    for (int i = 0; i < n; i++){
        for (int j = 0; j < n; j++){
            cin >> dist[i][j];
        }
    }
    
    int ans = INF;
    for (int i = 0; i < n; i++){
        vector<vector<int>> dp(1<<n, vector<int>(n, INF));
        using Pair = tuple<int, int, int>;
        priority_queue<Pair, vector<Pair>, greater<Pair>> pq;
        pq.emplace(0, 1<<i, i);
        while (!pq.empty()){
            auto [val, state, now] = pq.top(); pq.pop();
            
            if (dp[state][now] < INF) continue;
            dp[state][now] = val;
            
            if (__builtin_popcount(state) == m){
                //cerr << state << ' ' << now << " " << dp[state][now] << endl;
                for (int p = 0; p < k; p++){
                    ans = min(ans, dp[state][now] + dist[now][recieve[p]]);
                }
                continue;
            }
        

            for (int j = 0; j < n; j++){
                for (int p = 0; p < n; p++){
                    if ((state >> p) & 1) continue;
                    if (dp[state | 1<<p][p] < INF) continue;
                    int nval = dp[state][j] + dist[j][p];
                    pq.emplace(nval, state | (1<<p), p);
                }
            }
        }
    }
    
    cout << ans << endl;
        
    return 0;
}
0