結果
問題 | No.95 Alice and Graph |
ユーザー | tktk_snsn |
提出日時 | 2021-04-29 10:08:40 |
言語 | PyPy3 (7.3.15) |
結果 |
TLE
|
実行時間 | - |
コード長 | 1,146 bytes |
コンパイル時間 | 387 ms |
コンパイル使用メモリ | 86,880 KB |
実行使用メモリ | 294,028 KB |
最終ジャッジ日時 | 2023-09-22 18:04:59 |
合計ジャッジ時間 | 27,185 ms |
ジャッジサーバーID (参考情報) |
judge11 / judge13 |
(要ログイン)
テストケース
テストケース表示入力 | 結果 | 実行時間 実行使用メモリ |
---|---|---|
testcase_00 | AC | 2,855 ms
229,120 KB |
testcase_01 | AC | 497 ms
98,764 KB |
testcase_02 | AC | 476 ms
96,588 KB |
testcase_03 | AC | 87 ms
75,908 KB |
testcase_04 | AC | 4,380 ms
287,964 KB |
testcase_05 | AC | 4,153 ms
272,200 KB |
testcase_06 | AC | 3,890 ms
285,708 KB |
testcase_07 | AC | 482 ms
98,340 KB |
testcase_08 | AC | 91 ms
76,380 KB |
testcase_09 | AC | 72 ms
71,480 KB |
testcase_10 | AC | 77 ms
75,908 KB |
testcase_11 | AC | 87 ms
76,232 KB |
testcase_12 | AC | 89 ms
76,128 KB |
testcase_13 | TLE | - |
ソースコード
import sys input = sys.stdin.buffer.readline sys.setrecursionlimit(10 ** 7) inf = 10**9 N, M, K = map(int, input().split()) G = [[inf]*N for _ in range(N)] for i in range(N): G[i][i] = 0 for _ in range(M): a, b = map(int, input().split()) a -= 1 b -= 1 G[a][b] = 1 G[b][a] = 1 for k in range(N): for i in range(N): for j in range(N): if G[i][k] < inf and G[k][j] < inf: G[i][j] = min(G[i][j], G[i][k] + G[k][j]) node = [0] for p in reversed(range(1, N)): if len(node) > K: break node.append(p) sz = len(node) dp = [[inf]*sz for _ in range(1 << sz)] # mask:visited nodes, i:present dp[1][0] = 0 for bit in range(1, (1 << sz)-1): for i, s in enumerate(node): if (bit >> i) & 1: for j, t in enumerate(node): if i != j and ~(bit >> j) & 1: nxt_bit = bit | (1 << j) dp[nxt_bit][j] = min(dp[nxt_bit][j], dp[bit][i] + G[s][t]) if all(dp[(1 << sz)-1][i] > K for i in range(sz)): node.pop() ans = sum((1 << i)-1 for i in node) print(ans)