結果

問題 No.1190 Points
ユーザー qumazakiqumazaki
提出日時 2020-09-04 02:37:37
言語 PyPy3
(7.3.15)
結果
AC  
実行時間 340 ms / 2,000 ms
コード長 1,115 bytes
コンパイル時間 191 ms
コンパイル使用メモリ 82,164 KB
実行使用メモリ 114,868 KB
最終ジャッジ日時 2024-05-03 12:51:11
合計ジャッジ時間 7,563 ms
ジャッジサーバーID
（参考情報） 		judge2 / judge1
このコードへのチャレンジ
（要ログイン）

テストケース

テストケース表示
入力 結果 実行時間
実行使用メモリ
testcase_00 AC 38 ms
53,668 KB
testcase_01 AC 42 ms
55,872 KB
testcase_02 AC 42 ms
54,060 KB
testcase_03 AC 205 ms
103,980 KB
testcase_04 AC 181 ms
101,372 KB
testcase_05 AC 169 ms
98,872 KB
testcase_06 AC 238 ms
110,932 KB
testcase_07 AC 259 ms
114,552 KB
testcase_08 AC 256 ms
114,636 KB
testcase_09 AC 248 ms
113,996 KB
testcase_10 AC 267 ms
114,768 KB
testcase_11 AC 209 ms
107,488 KB
testcase_12 AC 258 ms
114,272 KB
testcase_13 AC 205 ms
102,968 KB
testcase_14 AC 88 ms
91,400 KB
testcase_15 AC 321 ms
114,652 KB
testcase_16 AC 94 ms
84,108 KB
testcase_17 AC 303 ms
111,108 KB
testcase_18 AC 148 ms
102,948 KB
testcase_19 AC 89 ms
91,768 KB
testcase_20 AC 177 ms
104,152 KB
testcase_21 AC 114 ms
92,476 KB
testcase_22 AC 109 ms
99,012 KB
testcase_23 AC 340 ms
114,784 KB
testcase_24 AC 317 ms
114,588 KB
testcase_25 AC 264 ms
114,868 KB
testcase_26 AC 136 ms
114,680 KB
testcase_27 AC 255 ms
114,728 KB
権限があれば一括ダウンロードができます

ソースコード

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