結果

問題 No.3158 Collect Stamps
ユーザー ゼリトキ
提出日時 2025-05-23 19:49:53
言語 C++23
(gcc 13.3.0 + boost 1.87.0)
結果
AC  
実行時間 178 ms / 2,000 ms
コード長 1,434 bytes
コンパイル時間 2,998 ms
コンパイル使用メモリ 276,580 KB
実行使用メモリ 9,088 KB
最終ジャッジ日時 2025-05-23 19:49:59
合計ジャッジ時間 6,160 ms
ジャッジサーバーID
（参考情報） 		judge4 / judge1
このコードへのチャレンジ
（要ログイン）
ファイルパターン 結果
sample AC * 3
other AC * 35
権限があれば一括ダウンロードができます

ソースコード

diff # 

#include <bits/stdc++.h>
using namespace std;
#define rep(i, n) for (ll i = 0; i < (ll)(n); i++)
#define ll long long
const long long mod=998244353;
const long long hmod=46216567629137;
int main(){
    cin.tie(0)->sync_with_stdio(0);
    cout.tie(0);
    int N,M,K;
    int A[20];
    int T[20][20];
    cin>>N>>M>>K;
    for(int i=1;i<=K;i++) cin>>A[i];
    for(int i=1;i<=N;i++){
        for(int j=1;j<=N;j++){
            cin>>T[i][j];
        }
    }
    int dp[20][70000];
    for(int i=1;i<=N;i++){
        for(int j=0;j<(1<<N);j++) dp[i][j]=1e9;
    }
    int pos=1;
    for(int i=1;i<=N;i++){
        dp[i][pos]=0;
        pos*=2;
    }
    for(int j=0;j<(1<<N);j++){
        for(int i=1;i<=N;i++){
            int wari=1;
            for(int k=1;k<=N;k++){
                if((j/wari)%2==0){
                    dp[k][j+wari]=min(dp[k][j+wari],dp[i][j]+T[i][k]);
                }
                wari*=2;
            }
        }
    }
    int ans=2e9;
    for(int i=1;i<=N;i++){
        for(int j=0;j<(1<<N);j++){
            int check=0;
            int wari=1;
            for(int k=1;k<=N;k++){
                if((j/wari)%2==1) check++;
                wari*=2;
            }
            int cnt=1e9;
            if(check>=M){
                for(int k=1;k<=K;k++){
                    cnt=min(cnt,T[i][A[k]]);
                }
            }
            ans=min(ans,dp[i][j]+cnt);
        }
    }
    cout<<ans<<"\n";
}
0