結果

問題 No.3158 Collect Stamps
コンテスト
ユーザー The Forsaking
提出日時 2025-05-23 19:56:50
言語 C++17
(gcc 13.3.0 + boost 1.87.0)
結果
AC  
実行時間 14 ms / 2,000 ms
コード長 814 bytes
コンパイル時間 1,780 ms
コンパイル使用メモリ 195,116 KB
実行使用メモリ 7,844 KB
最終ジャッジ日時 2025-05-23 19:57:04
合計ジャッジ時間 3,316 ms
ジャッジサーバーID
（参考情報） 		judge5 / judge3
このコードへのチャレンジ
（要ログイン）
ファイルパターン 結果
sample AC * 3
other AC * 35
権限があれば一括ダウンロードができます

ソースコード

diff # 

#include <bits/stdc++.h>

using namespace std;

typedef pair<int, int> pii;
typedef long long ll;
const int N = 2000086, MOD = 1e9 + 7, INF = 0x3f3f3f3f;
ll res;
int n, m, cnt, w[N];

int k;
int t[32][32];
bool st[50];

void dfs(int r, int sum, int f, int cost) {
	if (sum == m && st[r]) {
		res = min(res, (ll)cost);
		return;
	} else if (sum == m) {
		for (int i = 1; i < n + 1; i++)
			if (st[i])
				res = min(res, (ll)cost + t[r][i]);
		return;
	}

	for (int i = 1; i < n + 1; i++)
		if (!(f >> i & 1))
			dfs(i, sum + 1, f | (1 << i), cost + t[r][i]);
}

int main() {
	cin >> n >> m >> k;
	for (int i = 1, x; i < k + 1; i++) {
		cin >> x;
		st[x] = 1;
	}
	for (int i = 1; i < n + 1; i++)
		for (int j = 1; j < n + 1; j++)
			cin >> t[i][j];
	res = 1e18;
	dfs(0, 0, 0, 0);
	printf("%lld\n", res);
	return 0;
}
0