結果

問題 No.1190 Points
ユーザー qumazakiqumazaki
提出日時 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
このコードへのチャレンジ
（要ログイン）

テストケース

テストケース表示
入力 結果 実行時間
実行使用メモリ
testcase_00 AC 47 ms
53,248 KB
testcase_01 AC 47 ms
53,632 KB
testcase_02 AC 47 ms
53,376 KB
testcase_03 AC 227 ms
103,680 KB
testcase_04 AC 209 ms
100,992 KB
testcase_05 AC 198 ms
98,432 KB
testcase_06 AC 289 ms
110,592 KB
testcase_07 AC 296 ms
114,304 KB
testcase_08 AC 285 ms
114,176 KB
testcase_09 AC 280 ms
113,408 KB
testcase_10 AC 287 ms
114,304 KB
testcase_11 AC 249 ms
106,880 KB
testcase_12 AC 299 ms
114,176 KB
testcase_13 AC 240 ms
102,528 KB
testcase_14 AC 112 ms
91,136 KB
testcase_15 AC 380 ms
114,304 KB
testcase_16 AC 106 ms
83,840 KB
testcase_17 AC 342 ms
110,720 KB
testcase_18 AC 190 ms
102,528 KB
testcase_19 AC 115 ms
91,520 KB
testcase_20 AC 238 ms
104,064 KB
testcase_21 AC 150 ms
92,032 KB
testcase_22 AC 131 ms
98,688 KB
testcase_23 AC 405 ms
114,560 KB
testcase_24 AC 351 ms
114,432 KB
testcase_25 AC 294 ms
114,560 KB
testcase_26 AC 179 ms
114,176 KB
testcase_27 AC 300 ms
114,304 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