結果

問題 No.3463 Beltway
コンテスト
ユーザー まぬお
提出日時 2026-02-28 18:57:33
言語 PyPy3
(7.3.17)
コンパイル:
pypy3 -mpy_compile _filename_
実行:
pypy3 _filename_
結果
AC  
実行時間 1,042 ms / 2,000 ms
コード長 2,301 bytes
記録
記録タグの例:
初AC ショートコード 純ショートコード 純主流ショートコード 最速実行時間
コンパイル時間 2,372 ms
コンパイル使用メモリ 77,984 KB
実行使用メモリ 342,760 KB
最終ジャッジ日時 2026-02-28 18:57:44
合計ジャッジ時間 8,752 ms
ジャッジサーバーID
（参考情報） 		judge5 / judge4
このコードへのチャレンジ
（要ログイン）
ファイルパターン 結果
sample AC * 1
other AC * 17
権限があれば一括ダウンロードができます

ソースコード

diff #
raw source code 

from collections import deque, defaultdict, Counter
from bisect import bisect_left, bisect_right
from itertools import permutations, combinations, groupby
from heapq import heappop, heappush
import math, sys
input = lambda: sys.stdin.readline().rstrip("\r\n")
def printl(li, sep=" "): print(sep.join(map(str, li)))
def yn(flag): print(Yes if flag else No)
_int = lambda x: int(x)-1
MOD = 998244353 #10**9+7
INF = 1<<60
Yes, No = "Yes", "No"

import pypyjit, sys
pypyjit.set_param('max_unroll_recursion=-1')
sys.setrecursionlimit(10**6)

def find_bridges(n, edges):
    """
    n: 頂点数
    edges: (u, v) のリスト
    return: 各辺が橋なら1, そうでなければ0のリスト
    """
    E = [[] for _ in range(n)]
    for i, (u, v) in enumerate(edges):
        E[u].append((v, i))
        E[v].append((u, i))

    ord = [-1] * n
    low = [-1] * n
    is_bridge = [0] * len(edges)
    timer = 0

    def dfs(u, parent_edge_id=-1):
        nonlocal timer
        ord[u] = low[u] = timer
        timer += 1
        
        for v, edge_id in E[u]:
            if edge_id == parent_edge_id:
                continue
            if ord[v] != -1:
                low[u] = min(low[u], ord[v])
            else:
                dfs(v, edge_id)
                low[u] = min(low[u], low[v])
                if ord[u] < low[v]:
                    is_bridge[edge_id] = 1

    for i in range(n):
        if ord[i] == -1:
            dfs(i)
    return is_bridge
def ctypes(li, types):
    assert len(li) == len(types)
    return [t(a) for a, t in zip(li, types)]
def tinput(*types):
    li = input().split()
    return ctypes(li, types)
def qinput(*types):
    li = input().split()
    t = int(li[0])
    if len(li) == 1: return t, types[t-1][0](li[1])
    else: return t, ctypes(li[1:], types[t-1])
N, M, si, ti = tinput(int, int, _int, _int)
edges = []
for _ in range(M):
    u, v = map(_int, input().split())
    edges.append((u, v))

bridge = find_bridges(N, edges)
E = [[] for _ in range(N)]
for i in range(M):
    u, v = edges[i]
    E[u].append((v, bridge[i]))
    E[v].append((u, bridge[i]))

q = deque([si])
vis = [-1]*N
vis[si] = 0
while q:
    i = q.popleft()
    for j, e in E[i]:
        if vis[j] >= 0: continue
        vis[j] = vis[i]+(e^1)
        q.append(j)
print(vis[ti])
0