結果

提出番号	2334
提出者	efunyo
言語	Python3
提出日時	2020-03-24 22:24:16
問題名	(70)アルゴリズムのお勉強
結果	AC
点数	100%

---

テストケース

ソースコード

#https://kotamanegi.com/Problems/view/index.php?page=70

def main():
    import sys
    input = sys.stdin.readline
    sys.setrecursionlimit(10000000)
    from collections import Counter, deque
    #from collections import defaultdict
    from itertools import combinations, permutations, accumulate
    #from itertools import product
    from bisect import bisect_left,bisect_right
    import heapq
    from math import floor, ceil
    #from operator import itemgetter

    #inf = 10**17
    #mod = 10**9 + 7

    N = int(input())
    t = list(map(int, input().split()))
    a = [list(map(int, input().split())) for _ in range(N)]
    inf = 10**6

    #dp[s]:sは学習済みのアルゴリズム
    #         dp[s]はその時かかっている時間
    dp = [inf]*(1<<N)
    dp[0] = 0

    for s in range(1<<N):
        for i in range(N):
            if (s>>i) & 1:
                continue
            hiku = 0
            for j in range(N):
                if (s>>j) & 1:
                    hiku += a[j][i]
            ns = s |1<<i
            dp[ns] = min(dp[ns], dp[s]+t[i]-hiku)

    print(dp[-1])

if __name__ == '__main__':
    main()