結果

問題 No.3463 Beltway
コンテスト
ユーザー t5ugu
提出日時 2026-02-15 15:09:12
言語 PyPy3
(7.3.17)
コンパイル:
pypy3 -mpy_compile _filename_
実行:
pypy3 _filename_
結果
AC  
実行時間 631 ms / 2,000 ms
コード長 1,616 bytes
記録
記録タグの例:
初AC ショートコード 純ショートコード 純主流ショートコード 最速実行時間
コンパイル時間 358 ms
コンパイル使用メモリ 78,272 KB
実行使用メモリ 149,160 KB
最終ジャッジ日時 2026-02-28 15:50:35
合計ジャッジ時間 6,653 ms
ジャッジサーバーID
（参考情報） 		judge2 / judge3
このコードへのチャレンジ
（要ログイン）
ファイルパターン 結果
sample AC * 1
other AC * 17
権限があれば一括ダウンロードができます

ソースコード

diff #
raw source code 

from collections import deque

V, E, S, G = map(int, input().split())
can_go_from:list[list[int]] = [[] for _ in range(V+1)]
for _ in range(E):
    A, B = map(int, input().split())
    can_go_from[A].append(B)
    can_go_from[B].append(A)

Ord = [0]*(V+1)
Low = [0]*(V+1)

seen:set[int] = set()
dfs = deque([(S, 0)]) # queue of (vtx, parent)
trace:list[tuple[int,int]] = []
while dfs: # dfs for lowlink
    curr, pare = dfs.popleft()
    if curr in seen:
        continue
    seen.add(curr)
    Ord[curr] = Low[curr] = len(seen)
    for next in can_go_from[curr]:
        if next in seen and next != pare:
            Low[curr] = min(Ord[next], Low[curr]) # 行きがけの処理
        else:
            dfs.appendleft((next, curr))
    trace.append((curr, pare)) # 帰りがけ用

for curr, pare in reversed(trace):
    Low[pare] = min(Low[curr], Low[pare])

INF = 500_000
seen.clear()
min_step_from_S_to_G = INF
max_spent_circular_from_S_to_G = -1
bfs = deque([(S, 0, 0)]) # queue of (vtx, step, spent_circular)
# bfs for answer
while bfs:
    curr, step, cnt = bfs.popleft()
    if curr in seen: continue
    if curr == G:
        if step < min_step_from_S_to_G:
            min_step_from_S_to_G = step
            max_spent_circular_from_S_to_G = -1
        max_spent_circular_from_S_to_G = max(cnt,max_spent_circular_from_S_to_G)
    seen.add(curr) # このタイミングでの追加でよい説明は、あとで書く
    for next in can_go_from[curr]:
        if next not in seen:
            bfs.append((next, step + 1, cnt + (1 if Ord[curr] >= Low[next] else 0)))
print(max_spent_circular_from_S_to_G)
0