結果

問題 No.3158 Collect Stamps
ユーザー D M
提出日時 2025-09-19 15:12:45
言語 C++23
(gcc 13.3.0 + boost 1.87.0)
結果
AC  
実行時間 213 ms / 2,000 ms
コード長 1,033 bytes
コンパイル時間 5,964 ms
コンパイル使用メモリ 334,144 KB
実行使用メモリ 13,696 KB
最終ジャッジ日時 2025-09-19 15:12:54
合計ジャッジ時間 9,461 ms
ジャッジサーバーID
（参考情報） 		judge3 / 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 all(x) (x).begin(), (x).end()
using ll = long long;
const ll MOD = 998244353;
#include<atcoder/all>
using namespace atcoder;
using mint = modint998244353;

int main() {
  ios::sync_with_stdio(false);
  cin.tie(nullptr);
  ll n,m,k;cin>>n>>m>>k;
  vector<ll> A(k);
  rep(i,k) cin>>A[i];
  rep(i,k) A[i]--;
  vector<vector<ll>> T(n,vector<ll>(n));
  rep(i,n)rep(j,n) cin>>T[i][j];
  map<pair<set<ll>,ll>,ll> memo;
  function<ll(set<ll>,ll)> dfs=[&](set<ll> st,ll last){
    if(memo.count({st,last})) return memo[{st,last}];
    if(st.size()==m){
      ll m=LLONG_MAX;
      for(auto a:A){
        m=min(m,T[last][a]);
      }
      memo[{st,last}]=m;
      return m;
    }
    ll res=LLONG_MAX;
    rep(i,n){
      if(st.count(i)) continue;
      st.insert(i);
      res=min(res,dfs(st,i)+(last!=-1?T[last][i]:0));
      st.erase(i);
    }
    memo[{st,last}]=res;
    return res;
  };
  set<ll> st={};
  cout<<dfs(st,-1)<<'\n';
}
0