結果
問題 | No.2733 Just K-times TSP |
ユーザー |
|
提出日時 | 2024-03-23 18:33:32 |
言語 | PyPy3 (7.3.15) |
結果 |
AC
|
実行時間 | 1,032 ms / 2,000 ms |
コード長 | 638 bytes |
コンパイル時間 | 444 ms |
コンパイル使用メモリ | 81,792 KB |
実行使用メモリ | 141,440 KB |
最終ジャッジ日時 | 2024-10-11 13:07:34 |
合計ジャッジ時間 | 7,251 ms |
ジャッジサーバーID (参考情報) |
judge3 / judge2 |
(要ログイン)
ファイルパターン | 結果 |
---|---|
sample | AC * 2 |
other | AC * 32 |
ソースコード
from collections import defaultdictmod = 998244353N, M, K = map(int, input().split())g = [[] for _ in range(N)]for _ in range(M):u, v = map(int, input().split())u -= 1v -= 1g[u].append(v)g[v].append(u)dp = [[0] * N for _ in range((K + 1) ** N)]for i in range(N):dp[(K + 1) ** i][i] = 1for i in range((K + 1) ** N):for u in range(N):x = (i // ((K + 1) ** u)) % (K + 1)if 0 < x:for v in g[u]:y = (i // ((K + 1) ** v)) % (K + 1)if y < K:dp[i + (K + 1) ** v][v] += dp[i][u]dp[i + (K + 1) ** v][v] %= modans = 0for i in range(N):ans += dp[(K + 1) ** N - 1][i]ans %= modprint(ans)