結果

問題 No.3463 Beltway
コンテスト
ユーザー titia
提出日時 2026-06-22 16:29:39
言語 PyPy3
(7.3.17)
コンパイル:
pypy3 -mpy_compile _filename_
実行:
pypy3 _filename_
結果
AC  
実行時間 1,212 ms / 2,000 ms
コード長 2,758 bytes
記録
記録タグの例:
初AC ショートコード 純ショートコード 純主流ショートコード 最速実行時間
コンパイル時間 358 ms
コンパイル使用メモリ 85,588 KB
実行使用メモリ 257,700 KB
最終ジャッジ日時 2026-06-22 16:29:55
合計ジャッジ時間 15,083 ms
ジャッジサーバーID
（参考情報） 		judge2_1 / judge1_1
このコードへのチャレンジ
（要ログイン）
ファイルパターン 結果
sample AC * 1
other AC * 17
権限があれば一括ダウンロードができます

ソースコード

diff #
raw source code 

import sys
input = sys.stdin.readline

from heapq import heappop,heappush

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=[]
Q.append((0,0,S-1))

while Q:
    #print(Q)
    distance,cost,ind=heappop(Q)
    cost=-cost
    if DP[ind]!=[distance,cost]:
        continue


    for to in EDGE[ind]:
        #print(x,to)
        if not (to in ELIST2[ind]):
            #print(to)
            if DP[to][0]>distance+1:
                DP[to]=[distance+1,cost+1]
                heappush(Q,(distance+1,-(cost+1),to))
                
            elif DP[to][0]==distance+1 and DP[to][1]<cost+1:
                DP[to]=[distance+1,cost+1]
                heappush(Q,(distance+1,-(cost+1),to))
        else:
            if DP[to][0]>distance+1:
                DP[to]=[distance+1,cost]
                heappush(Q,(distance+1,-cost,to))
            elif DP[to][0]==distance+1 and DP[to][1]<cost:
                DP[to]=[distance+1,cost]
                heappush(Q,(distance+1,-cost,to))
            

if DP[G-1][0]>(1<<30):
    print(-1)
else:
    print(DP[G-1][1])
0