結果

問題 No.3158 Collect Stamps
ユーザー Rumain831
提出日時 2025-05-23 20:44:12
言語 C++17
(gcc 13.3.0 + boost 1.87.0)
結果
AC  
実行時間 47 ms / 2,000 ms
コード長 1,469 bytes
コンパイル時間 1,430 ms
コンパイル使用メモリ 107,852 KB
実行使用メモリ 7,844 KB
最終ジャッジ日時 2025-05-23 20:44:16
合計ジャッジ時間 3,242 ms
ジャッジサーバーID
（参考情報） 		judge2 / judge3
このコードへのチャレンジ
（要ログイン）
ファイルパターン 結果
sample AC * 3
other AC * 35
権限があれば一括ダウンロードができます

ソースコード

diff # 

#include<iostream>
#include<vector>
#include<set>
#include<math.h>
#include<algorithm>
using namespace std;
using ll = long long;

int main(void){
  int n, m, k; cin >> n >> m >> k;
  vector<int> stamp(n), a(k);
  for(int i=0; i<k; i++){
    cin >> a[i]; a[i]--;
    stamp[a[i]]++;
  }
  vector t(n+1, vector<ll>(n+1));
  for(int i=0; i<n; i++)for(int j=0; j<n; j++) cin >> t[i][j];
  ll ans=1e18;
  auto dfs=[&](auto dfs, ll sum, int now, int step, set<int>& visited, vector<int>& path)->void{
    for(int i=0; i<n; i++){
      if(visited.count(i)) continue;
      visited.insert(i);
      path.push_back(i);
      sum+=t[now][i];
      //cout << now << ' ' << i << ' ' << t[now][i] << ' ' << sum << endl;
      if(visited.size()==m){
        //cout << "! " << i << ' ';
        //for(auto q:path) cout << q << ' '; cout << sum << endl;
        if(stamp[i]){
          ans=min(ans, sum);
        }
        else{
          for(int j=0; j<k; j++){
            if(visited.count(a[j])) continue;
            else{
              ans=min(ans, sum+t[i][a[j]]);
            }
          }
        }
        sum-=t[now][i];
        visited.erase(i);
        path.pop_back();
        continue;
      }
      dfs(dfs, sum, i, step+1, visited, path);
      sum-=t[now][i];
      visited.erase(i);
      path.pop_back();
    }
    return;
  };
  //for(int i=0; i<n; i++){
    set<int> vis;
    vector<int> q;
    dfs(dfs, 0, n, 0, vis, q);
  //}
  cout << ans << endl;
  return 0;
}
0