結果

問題 No.3291 K-step Navigation
コンテスト
ユーザー LyricalMaestro
提出日時 2025-10-04 18:25:42
言語 PyPy3
(7.3.15)
結果
WA  
実行時間 -
コード長 2,656 bytes
コンパイル時間 2,962 ms
コンパイル使用メモリ 81,980 KB
実行使用メモリ 77,996 KB
最終ジャッジ日時 2025-10-04 18:26:06
合計ジャッジ時間 16,780 ms
ジャッジサーバーID
（参考情報） 		judge5 / judge4
このコードへのチャレンジ
（要ログイン）
ファイルパターン 結果
sample AC * 2
other AC * 40 WA * 11
権限があれば一括ダウンロードができます

ソースコード

diff # 

# https://yukicoder.me/problems/no/3291

from collections import deque

MAX_VALUE = 10 ** 18

def main():
    N, M, K, s, t = map(int, input().split())
    s -= 1
    t -= 1
    edge_set = set()
    next_nodes = [[] for _ in range(N)]
    edge_set
    for _ in range(M):
        u, v = map(int, input().split())
        next_nodes[u - 1].append(v - 1)
        next_nodes[v - 1].append(u - 1)

        u0 = min(u - 1, v - 1)
        v0 = max(u - 1, v-  1)
        edge_set.add((u0, v0))

    dp_from_start = [[MAX_VALUE] * N for _ in range(2)]
    dp_from_start[0][s] = 0
    queue = deque()
    queue.append((0, s))
    while len(queue) > 0:
        state, v = queue.popleft()
        new_state = 1 - state
        for w in next_nodes[v]:
            if dp_from_start[new_state][w] == MAX_VALUE:
                dp_from_start[new_state][w] = dp_from_start[state][v] + 1
                queue.append((new_state, w))
    
    k = dp_from_start[0][t]
    if k <= K and (K - k) % 2 == 0:
        print("Yes")
        return
    k = dp_from_start[1][t]
    if k <= K and (K - k) % 2 == 0:
        print("Yes")
        return
    
    # 今度は追加してうまく行くかをみる
    dp_from_goal0 = [[MAX_VALUE] * N for _ in range(2)]
    dp_from_goal0[0][t] = 0
    queue = deque()
    queue.append((0, t))
    while len(queue) > 0:
        state, v = queue.popleft()
        new_state = 1 - state
        for w in next_nodes[v]:
            if dp_from_goal0[new_state][w] == MAX_VALUE:
                dp_from_goal0[new_state][w] = dp_from_goal0[state][v] + 1
                queue.append((new_state, w))
    dp_from_goal1 = [[MAX_VALUE] * N for _ in range(2)]
    dp_from_goal1[1][t] = 0
    queue = deque()
    queue.append((1, t))
    while len(queue) > 0:
        state, v = queue.popleft()
        new_state = 1 - state
        for w in next_nodes[v]:
            if dp_from_goal1[new_state][w] == MAX_VALUE:
                dp_from_goal1[new_state][w] = dp_from_goal1[state][v] + 1
                queue.append((new_state, w))
    
    for u0 in range(N):
        for v0 in range(u0 + 1, N):
            edge = (u0, v0)
            if edge not in edge_set:
                for i0 in range(2):
                    for j0 in range(2):
                        for k in range(2):
                            u = edge[k]
                            v = edge[1 - k]
                            a0 = dp_from_start[i0][u] + 1 + dp_from_goal0[j0][v]
                            if K >= a0 and (K - a0) % 2 == 0:
                                print("Yes")
                                return
    print("No")







if __name__ == "__main__":
    main()
0