Submission #27843

ソースコード

?
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
n, m, s = map(int, input().split())
s -= 1
infinity = 1000000000
distance = [[infinity] * n for _ in range(n)]
for i in range(m):
a, b, c = map(int, input().split())
a -= 1
b -= 1
distance[a][b] = min(distance[a][b], c)
distance[b][a] = min(distance[b][a], c)
# Warshall-Floyd hou
for k in range(n):
for i in range(n):
for j in range(n):
distance[i][j] = min(
distance[i][j], distance[i][k] + distance[k][j])
dp = [[infinity] * n for _ in range(1 << n)]
dp[0][s] = 0
for bag in range(1, 1 << n):
for i in range(n):
tmp = 1000000000
if (bag & 1 << i) == 0:
continue
for j in range(n):
if i != j:
tmp = min(tmp, dp[bag ^ 1 << i][j] + distance[j][i])
dp[bag][i] = tmp
print(dp[(1 << n) - 1][s])

ステータス

項目 データ
問題 0010 - クッキー
ユーザー名 KirikaYuumura
投稿日時 2017-10-25 12:55:26
言語 Python3
状態 Accepted
得点 35
ソースコード長 862 Byte
最大実行時間 81 ms
最大メモリ使用量 4296 KB

セット

セット 得点 Cases
1 小課題１ 5 / 5 cookies_input1.txt
2 小課題２ 10 / 10 cookies_input2.txt
3 小課題３ 20 / 20 cookies_input3.txt

テストケース

ファイル名 状態 実行時間 メモリ使用量 #
cookies_input1.txt AC 47 ms 4228 KB
1
cookies_input2.txt AC 81 ms 4296 KB
2
cookies_input3.txt AC 78 ms 4152 KB
3