結果

問題 No.1190 Points
ユーザー lam6er
提出日時 2025-03-20 20:26:40
言語 PyPy3
(7.3.15)
結果
WA  
実行時間 -
コード長 1,498 bytes
コンパイル時間 161 ms
コンパイル使用メモリ 82,172 KB
実行使用メモリ 111,280 KB
最終ジャッジ日時 2025-03-20 20:27:51
合計ジャッジ時間 5,932 ms
ジャッジサーバーID
（参考情報） 		judge1 / judge5
このコードへのチャレンジ
（要ログイン）
ファイルパターン 結果
sample AC * 3
other AC * 13 WA * 12
権限があれば一括ダウンロードができます

ソースコード

diff # 

import sys
from collections import deque

def main():
    input = sys.stdin.read().split()
    ptr = 0
    N, M, P = map(int, input[ptr:ptr+3])
    ptr +=3
    S, G = map(int, input[ptr:ptr+2])
    ptr +=2
    S -=1  # convert to 0-based index
    G -=1

    adj = [[] for _ in range(N)]
    for _ in range(M):
        u, v = map(int, input[ptr:ptr+2])
        ptr +=2
        u -=1
        v -=1
        adj[u].append(v)
        adj[v].append(u)

    def bfs(start, adj_list):
        dist = [ -1 ] * N
        q = deque([start])
        dist[start] = 0
        while q:
            u = q.popleft()
            for v in adj_list[u]:
                if dist[v] == -1:
                    dist[v] = dist[u] +1
                    q.append(v)
        return dist

    d1 = bfs(S, adj)
    # Compute distance from G to all nodes, reverse adj
    rev_adj = [[] for _ in range(N)]
    for u in range(N):
        for v in adj[u]:
            rev_adj[v].append(u)
    d2 = bfs(G, rev_adj)

    if d2[S] == -1:
        print(-1)
        return

    result = []
    for u in range(N):
        if d1[u] == -1 or d2[u] == -1:
            continue
        sum_d = d1[u] + d2[u]
        if sum_d > P:
            continue
        rem = P - sum_d
        if rem >=0 and rem %2 ==0:
            result.append(u+1)  # revert to 1-based

    if not result:
        print(-1)
    else:
        result.sort()
        print(len(result))
        print('\n'.join(map(str, result)))

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