結果

問題 No.1190 Points
コンテスト
ユーザー qumazaki
提出日時 2020-09-04 02:37:37
言語 PyPy3
(7.3.15)
結果
AC  
実行時間 405 ms / 2,000 ms
コード長 1,115 bytes
コンパイル時間 229 ms
コンパイル使用メモリ 82,304 KB
実行使用メモリ 114,560 KB
最終ジャッジ日時 2024-11-24 12:51:14
合計ジャッジ時間 9,326 ms
ジャッジサーバーID
（参考情報） 		judge2 / judge4
このコードへのチャレンジ
（要ログイン）
ファイルパターン 結果
sample AC * 3
other AC * 25
権限があれば一括ダウンロードができます

ソースコード

diff # 

import sys
read = sys.stdin.buffer.read
readline = sys.stdin.buffer.readline
readlines = sys.stdin.buffer.readlines

n,m,p = map(int,readline().split())
s,g = map(int,readline().split())
data = list(map(int,read().split()))

from collections import deque
def dfs(links, start, n):
    inf = 10**10
    d = [inf] * (n)
    d[start] = 0
    dq = deque()
    dq.append(start)
    while(dq):
        i = dq.popleft()
        for j in links[i]:
            if(d[j] != inf):
                continue
            d[j] = d[i]+1
            dq.append(j)
    return d

links = [[] for _ in range(2*n+1)]

it = iter(data)
for u,v in zip(it,it):
    links[u].append(v+n)
    links[v].append(u+n)
    links[u+n].append(v)
    links[v+n].append(u)

ds = dfs(links,s,2*n+1)
dg = dfs(links,g,2*n+1)

ans = []
if(p%2==0):
    for i in range(1,n+1):
        if(ds[i] + dg[i] <= p)|(ds[i+n] + dg[i+n] <= p):
            ans.append(i)
else:
    for i in range(1,n+1):
        if(ds[i] + dg[i+n] <= p)|(ds[i+n] + dg[i] <= p):
            ans.append(i)

if(ans):
    print(len(ans))
    print('\n'.join(map(str,ans)))
else:
    print(-1)
0