結果

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

ソースコード

diff # 

#include <bits/stdc++.h>
#include <atcoder/all>
using namespace std;
using namespace atcoder;
typedef long long ll;
typedef long double ld;
#define sz(c) ((ll)(c).size())
#define ALL(x) x.begin(),x.end()
#define LB(A,x) (ll)(lower_bound(ALL(A),x)-A.begin())
#define UB(A,x) (ll)(upper_bound(ALL(A),x)-A.begin())
#define BS(A,x) binary_search(ALL(A),x)
#define rep(i,a,b) for(int i=a;i<b;i++)
template<class T>bool chmax(T& a, const T& b) { if (a < b) { a = b; return 1; } return 0; }
template<class T>bool chmin(T& a, const T& b) { if (b < a) { a = b; return 1; } return 0; }
using vi = vector<int>; 
using vvi = vector<vi>; 
using li =vector<ll>;
using lli=vector<li>;
const long long mod=998244353;
int main(){
	ll n,m,k;cin>>n>>m>>k;
	vi A(n);
	lli T(n,li(n));
	rep(i,0,k){
		int a;cin>>a;a--;A[a]++;
	}
	rep(i,0,n)rep(j,0,n)cin>>T[i][j];
	ll ans=1e18;
	if(m==1){cout<<0;return 0;}
	rep(i,0,n){
		lli dp((1LL<<n),li(n,1e18));
		dp[(1LL<<i)][i]=0;
		rep(j,0,(1LL<<n)){
			int cnt=0;
			rep(p,0,n)if((j>>p)%2==1)cnt++;
			//現在地
			rep(p,0,n){
				if((j>>p)%2==0)continue;
				//向かう頂点
				rep(q,0,n){
					//すでに行ったことがある
					if((j>>q)%2==1){
						if(cnt>=m&&A[q]==1)ans=min(ans,dp[j][p]+T[p][q]);
					}
					else {
						if(cnt+1>=m&&A[q]==1)ans=min(ans,dp[j][q]+T[p][q]);
						dp[j+(1LL<<q)][q]=min(dp[j+(1LL<<q)][q],dp[j][p]+T[p][q]);
					}
				}
			}
		}
	}
	cout<<ans;
}
0