Submission #30845076

Source Code Expand

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

Submission Time
Task C - 巡回セールスマン問題
User Pro_ktmr
Language PyPy3 (7.3.0)
Score 100
Code Size 503 Byte
Status AC
Exec Time 89 ms
Memory 73928 KiB

Judge Result

Set Name Sample All
Score / Max Score 0 / 0 100 / 100
Status
AC × 1
AC × 22
Set Name Test Cases
Sample sample_001.txt
All sample_001.txt, data_001.txt, data_002.txt, data_003.txt, data_004.txt, data_005.txt, data_006.txt, data_007.txt, data_008.txt, data_009.txt, data_010.txt, data_011.txt, data_012.txt, data_013.txt, data_014.txt, data_015.txt, data_016.txt, data_017.txt, data_018.txt, data_019.txt, data_020.txt, sample_001.txt
Case Name Status Exec Time Memory
data_001.txt AC 74 ms 68448 KiB
data_002.txt AC 58 ms 67932 KiB
data_003.txt AC 64 ms 69360 KiB
data_004.txt AC 48 ms 61344 KiB
data_005.txt AC 71 ms 73388 KiB
data_006.txt AC 48 ms 61452 KiB
data_007.txt AC 50 ms 61736 KiB
data_008.txt AC 49 ms 61532 KiB
data_009.txt AC 50 ms 61424 KiB
data_010.txt AC 85 ms 73760 KiB
data_011.txt AC 49 ms 61692 KiB
data_012.txt AC 89 ms 73928 KiB
data_013.txt AC 67 ms 69544 KiB
data_014.txt AC 55 ms 65288 KiB
data_015.txt AC 55 ms 65200 KiB
data_016.txt AC 51 ms 61356 KiB
data_017.txt AC 49 ms 61288 KiB
data_018.txt AC 49 ms 61548 KiB
data_019.txt AC 89 ms 73780 KiB
data_020.txt AC 57 ms 68056 KiB
sample_001.txt AC 53 ms 61304 KiB