結果

問題 No.3463 Beltway
コンテスト
ユーザー titia
提出日時 2026-06-22 16:19:34
言語 PyPy3
(7.3.17)
コンパイル:
pypy3 -mpy_compile _filename_
実行:
pypy3 _filename_
結果
MLE  
実行時間 -
コード長 2,419 bytes
記録
記録タグの例:
初AC ショートコード 純ショートコード 純主流ショートコード 最速実行時間
コンパイル時間 396 ms
コンパイル使用メモリ 85,088 KB
実行使用メモリ 859,980 KB
最終ジャッジ日時 2026-06-22 16:19:56
合計ジャッジ時間 4,687 ms
ジャッジサーバーID
（参考情報） 		judge2_0 / judge3_0
このコードへのチャレンジ
（要ログイン）
ファイルパターン 結果
sample AC * 1
other AC * 3 MLE * 1 -- * 13
権限があれば一括ダウンロードができます

ソースコード

diff #
raw source code 

import sys
input = sys.stdin.readline

from collections import deque

V,E,S,G=list(map(int,input().split()))

EDGE2=[list(map(int,input().split())) for i in range(E)]

for i in range(E):
    EDGE2[i][0]-=1
    EDGE2[i][1]-=1

EDGE = [[] for i in range(V)]  # 隣接リスト

for x,y in EDGE2:
    EDGE[x].append(y)
    EDGE[y].append(x)

ROOT = 0 # ROOTを定める。
Q = [(ROOT, ROOT)]
USE = [0]*V
DFS_ORD = [0]*V  # DFSした順に番号をつける。DFS_ORD[i]=xで、頂点iの次数はx
DFS_SORT = []  # DFSで見た頂点の順番。
DFS_Parent = [-1]*V  # DFS木の親
DFS_Child = [[] for i in range(V)]
LOWLINK = [0]*V  # LOWLINK。後退辺を一回まで使ってたどりつける次数（DFSで何番目にたどりついたか）の最小値。
ordnum = 1

while Q:
    fr, x = Q.pop()
    if USE[x] == 1:
        continue
    DFS_SORT.append(x)
    if fr != x:
        DFS_Parent[x] = fr
        DFS_Child[fr].append(x)
        DFS_ORD[x] = ordnum
        ordnum += 1
        LOWLINK[x] = DFS_ORD[x]  # LOWLINKをDFS_ORDで初期化。

    USE[x] = 1

    for to in EDGE[x]:
        if USE[to] == 0:
            Q.append((x, to))

for i in DFS_SORT[::-1]:  # DFS_ORDの大きい頂点から順番に見て、LOWLINKを更新していく。
    for to in EDGE[i]:
        if to != DFS_Parent[i]:
            LOWLINK[i] = min(LOWLINK[i], DFS_ORD[to], LOWLINK[to])

BRIDGES = []
for i in range(V): # DFS木の各辺を調べる。
    if i==ROOT:
        continue
    if DFS_ORD[DFS_Parent[i]] < LOWLINK[i]: # DFS木の辺uvが橋になるのは、子のLOWLINKが親のDFS_ORDより大きいとき。
        BRIDGES.append(sorted((i,DFS_Parent[i])))



ELIST2 = [set() for i in range(V)]

for x,y in BRIDGES:
    ELIST2[x].add(y)
    ELIST2[y].add(x)

DP=[[1<<60,0] for i in range(V)]

DP[S-1]=[0,0]
Q=deque()
Q.append(S-1)

while Q:
    x=Q.popleft()
    now,m=DP[x]

    for to in EDGE[x]:
        if not (to in ELIST2[x]):
            if DP[to][0]>now+1:
                DP[to]=[now+1,m+1]
                Q.append(to)
            elif DP[to][0]==now and DP[to][1]<m+1:
                DP[to]=[now+1,m+1]
                Q.append(to)
        else:
            if DP[to][0]>now+1:
                DP[to]=[now+1,m]
                Q.append(to)
            elif DP[to][0]==now and DP[to][1]<m:
                DP[to]=[now+1,m]
                Q.append(to)
            
            
print(DP[G-1][1])
0