結果

問題 No.2948 move move rotti
ユーザー i_taku
提出日時 2025-03-26 12:02:56
言語 PyPy3
(7.3.15)
結果
AC  
実行時間 1,605 ms / 4,000 ms
コード長 957 bytes
コンパイル時間 467 ms
コンパイル使用メモリ 82,092 KB
実行使用メモリ 134,852 KB
最終ジャッジ日時 2025-03-26 12:03:23
合計ジャッジ時間 23,530 ms
ジャッジサーバーID
（参考情報） 		judge1 / judge4
このコードへのチャレンジ
（要ログイン）
ファイルパターン 結果
sample AC * 3
other AC * 28
権限があれば一括ダウンロードができます

ソースコード

diff # 

def solve(s):
    dp = [[False] * (1 << N) for _ in range(N)]
    dp[s][1 << s] = True
    for i in range(1 << N):
        for j in range(N):
            if i >> j & 1 == 0:
                continue
            for k in range(N):
                if i >> k & 1:
                    continue
                dp[k][i | 1 << k] |= dp[j][i] and g[j][k]
    return dp

N, M, K = map(int, input().split())
X = [int(x) - 1 for x in input().split()]
g = [[False] * N for _ in range(N)]
for _ in range(M):
    u, v = map(int, input().split())
    u, v = u - 1, v - 1
    g[u][v] = g[v][u] = True

dp = [[[False] * N for _ in range(N)] for _ in range(N)]
for x in X:
    res = solve(x)
    for i in range(1 << N):
        for j in range(N):
            dp[x][i.bit_count() - 1][j] |= res[j][i]

# i回目にjで合流できるか
for i in range(N):
    for j in range(N):
        if all(dp[x][i][j] for x in X):
            print('Yes')
            exit()
print('No')
0