結果

問題 No.3158 Collect Stamps
コンテスト
ユーザー ID 21712
提出日時 2025-06-09 01:22:56
言語 Go
(1.23.4)
結果
AC  
実行時間 30 ms / 2,000 ms
コード長 981 bytes
コンパイル時間 12,055 ms
コンパイル使用メモリ 252,548 KB
実行使用メモリ 8,112 KB
最終ジャッジ日時 2025-06-09 01:23:12
合計ジャッジ時間 14,004 ms
ジャッジサーバーID
（参考情報） 		judge2 / judge3
このコードへのチャレンジ
（要ログイン）
ファイルパターン 結果
sample AC * 3
other AC * 35
権限があれば一括ダウンロードができます

ソースコード

diff # 

package main

import . "fmt"

func main() {
	var n, m, k int
	Scan(&n,&m,&k)
	s := make([]bool, n)
	for i := 0; i < k; i++ {
		var a int
		Scan(&a)
		s[a-1] = true
	}
	t := make([][]int, n)
	for i := range t {
		t[i] = make([]int, n)
		for j := range t[i] {
			Scan(&t[i][j])
		}
	}
	ps := perm(m)
	ans := int(1e9)
	for i := 0; i < (1<<n); i++ {
		es := []int{}
		for j := 0; j < n; j++ {
			if (i&(1<<j))!= 0 {
				es=append(es, j)
			}
		}
		if len(es) != m {
			continue
		}
		for _, p := range ps {
			if !s[es[p[m-1]]] {
				continue
			}
			cnt := 0
			for j := range p[1:] {
				cnt += t[es[p[j]]][es[p[j+1]]]
			}
			ans = min(ans, cnt)
		}
	}
	Println(ans)
}

func perm(m int) [][]int {
	ret := [][]int{}
	p := make([]int, m)
	var dfs func(d, x int)
	dfs = func(d, x int) {
		if d == m {
			ret = append(ret, append([]int{}, p...))
		} else {
			for i := 0; i < m; i++ {
				if ((1<<i)&x)== 0{
					p[d] = i
					dfs(d+1,x|(1<<i))
				}
			}
		}
	}
	dfs(0,0)
	return ret
}
0