Submission #30845076

Source Code Expand

1
2
3
4
5
6
7
8
9
10
11
12
13
14
INF = 10 ** 18
n = int(input())
a = [[0] * n for i in range(n)]
for i in range(n):
    a[i] = list(map(int, input().split()))
dp = [[INF] * (1 << n) for i in range(n)] # (1 << n) は 2 の n 乗
dp[0][0] = 0
for j in range(1 << n):
    for i in range(n):
        for k in range(n):
            if (j >> k) & 1 == 0:
                continue
            dp[i][j] = min(dp[i][j], dp[k][j - (1 << k)] + a[k][i])
print(dp[0][(1 << n) - 1]) # (1 << n) - 1 は二進法で n 桁 1 が並んだ数
 
 
הההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההה
XXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXX

INF = 10 ** 18
n = int(input())
a = [[0] * n for i in range(n)]
for i in range(n):
    a[i] = list(map(int, input().split()))
dp = [[INF] * (1 << n) for i in range(n)] # (1 << n) は 2 の n 乗
dp[0][0] = 0
for j in range(1 << n):
    for i in range(n):
        for k in range(n):
            if (j >> k) & 1 == 0:
                continue
            dp[i][j] = min(dp[i][j], dp[k][j - (1 << k)] + a[k][i])
print(dp[0][(1 << n) - 1]) # (1 << n) - 1 は二進法で n 桁 1 が並んだ数

Submission Info

Judge Result