結果

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

ソースコード

diff # 

//#define _GLIBCXX_DEBUG
#include <bits/stdc++.h>
using namespace std;
#define rep(i, n) for (ll i = 0; i < (ll)(n); i++)
#define all(a) (a).begin(), (a).end()
using ll = long long;
const ll INF32 = 2e9;
const ll INF64 = 4e18;

vector<int> dist;
int N, M, K;
vector<int> A;
vector<vector<int>> T;

void printYN(bool ok){
    if(ok)cout << "Yes" << endl;
    else cout << "No" << endl;
    return;
}

void dfs(int v, int d, int cnt, set<int> &seen){
    if(cnt==M){
        dist[v] = min(dist[v], d);
        return;
    }
    rep(i, N){
        if(seen.count(i))continue;
        seen.insert(i);
        dfs(i, d+T[v][i], cnt+1, seen);
        seen.erase(i);
    }
}

int main() {
    cin >> N >> M >> K;
    A.resize(K);
    rep(i, K){
        cin >> A[i];
        A[i]--;
    }
    dist.resize(N, INF32);
    T.resize(N, vector<int>(N));
    rep(i, N) rep(j, N)cin >> T[i][j];
    rep(i, N){
        set<int> seen;
        seen.insert(i);
        dfs(i, 0, 1, seen);
    }
    vector<bool> ok(N, false);
    priority_queue<pair<int, int>, vector<pair<int, int>>, greater<pair<int, int>>> que;
    rep(i, N)que.push({dist[i], i});
    while(!que.empty()){
        auto fr = que.top();
        int d = fr.first;
        int v = fr.second;
        que.pop();
        if(ok[v])continue;
        ok[v] = true;
        for(int i = 0; i < N; i++){
            if(i == v)continue;
            if(dist[i] > d + T[v][i]){
                dist[i] = d + T[v][i];
                que.push({dist[i], i});
            }
        }
    }
    int ans = INF32;
    rep(i, K){
        ans = min(ans, dist[A[i]]);
    }
    cout << ans << endl;
    return 0;
}
0