結果

提出番号	2413
提出者	awk_138
言語	Python3
提出日時	2020-10-24 19:23:30
問題名	(70)アルゴリズムのお勉強
結果	WA
点数	0%

テストケース

テストケース	結果	得点	実行時間	メモリ使用量
1	WA	0%	21ms	33104KB
2	WA	0%	21ms	32720KB
3	WA	0%	22ms	33264KB
4	WA	0%	25ms	32928KB
5	WA	0%	21ms	32912KB
6	WA	0%	26ms	33168KB
7	WA	0%	21ms	32992KB
8	WA	0%	31ms	33024KB
9	WA	0%	20ms	32624KB
10	WA	0%	21ms	33008KB
11	WA	0%	52ms	34992KB
12	WA	0%	33ms	34160KB
13	WA	0%	52ms	35104KB
14	WA	0%	34ms	33952KB
15	WA	0%	33ms	35216KB
16	WA	0%	22ms	32816KB
17	WA	0%	22ms	33072KB
18	WA	0%	21ms	33008KB
19	WA	0%	91ms	36032KB
20	WA	0%	93ms	36272KB
21	WA	0%	23ms	32800KB
22	WA	0%	184ms	37376KB
23	WA	0%	26ms	33392KB
24	WA	0%	403ms	43088KB
25	WA	0%	99ms	35760KB
26	WA	0%	188ms	38736KB
27	WA	0%	410ms	43312KB
28	WA	0%	91ms	35936KB
29	TLE	0%	2021ms	80832KB
30	WA	0%	185ms	38656KB

ソースコード

def rec(bit, v, dist, dp, N):
    if dp[bit][v] != -1:
        return dp[bit][v]
    
    if bit == (1<<v):
        dp[bit][v] = 0
        return dp[bit][v]
    
    res = -float('inf')
    prev_bit = bit & ~(1<<v)

    for u in range(N):
        if not(prev_bit & (1<<u)):
            continue

        res = max(res, rec(prev_bit, u, dist, dp, N) + dist[u][v])
        if v == 0:
            print(rec(prev_bit, u, dist, dp, N))
            print(dist[u][v])

    dp[bit][v] = res
    return res

def solve():
    N = int(input())
    t = list(map(int, input().split()))
    dist = [list(map(int,input().split())) for _ in range(N)]
    
    res = -float('inf')
    dp = [[-1] * N for _ in range((1<<N))]
    for v in range(N):
        res = max(res, rec((1<<N)-1, v, dist, dp, N))
    
    print(max(0,sum(t) - res))

if __name__ == '__main__':
    solve()

結果

テストケース

ALL0%/100%

ソースコード