結果

問題 No.90 品物の並び替え
コンテスト
ユーザー fmhr
提出日時 2017-01-28 15:52:08
言語 Go
(1.23.4)
結果
AC  
実行時間 2 ms / 5,000 ms
コード長 774 bytes
コンパイル時間 11,224 ms
コンパイル使用メモリ 233,628 KB
実行使用メモリ 5,248 KB
最終ジャッジ日時 2024-12-23 21:05:37
合計ジャッジ時間 11,945 ms
ジャッジサーバーID
（参考情報） 		judge4 / judge3
このコードへのチャレンジ
（要ログイン）
ファイルパターン 結果
sample AC * 1
other AC * 9
権限があれば一括ダウンロードができます

ソースコード

diff # 

package main

import "fmt"

func main() {
	var N uint
	var M int
	fmt.Scan(&N, &M)
	var t [100][100]uint
	var a, b int
	var c uint
	for i := 0; i < M; i++ {
		fmt.Scan(&a, &b, &c)
		t[a][b] = c
	}
	var d [512]uint
	for i := 0; i < 1<<N; i++ {
		for j := uint(0); j < N; j++ {
			// すでに使ってる
			if i&(1<<j) != 0 {
				continue
			}
			// nはビットで使用したアイテムを表してる
			n := i | 1<<j
			s := d[i]
			for k := uint(0); k < N; k++ {
				if i&(1<<k) == 0 {
					continue
				}
				// まだ使ってないアイテムk,jの値を足す
				s += t[k][j]
			}
			d[n] = max(s, d[n])
		}
	}
	fmt.Println(d[1<<N-1])
}

func max(a, b uint) uint {
	if a > b {
		return a
	}
	return b
}

// 参照http://yukicoder.me/submissions/76498
// bitDP?
0