結果

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

ソースコード

diff #
raw source code 

import sys
input = lambda :sys.stdin.readline()[:-1]
ni = lambda :int(input())
na = lambda :list(map(int,input().split()))
yes = lambda :print("yes");Yes = lambda :print("Yes");YES = lambda : print("YES")
no = lambda :print("no");No = lambda :print("No");NO = lambda : print("NO")
#######################################################################
class LowLink:
    def __init__(self, adj: list[list[int]]):
        self.n = n = len(adj)
        order = [-1] * n
        low = [n] * n
        par = [-1] * n
        children = [[] for _ in range(n)]

        seen = [0] * n
        idx = 0
        for u in range(n):
            if order[u] != -1:
                continue
            seen[u] = 1
            st = [u]
            par[u] = -2
            while st:
                v = st.pop()
                if v >= 0:
                    if order[v] != -1:
                        continue
                    order[v] = idx
                    low[v] = idx
                    idx += 1
                    if v != u:
                        children[par[v]].append(v)
                        st.append(~v)
                    check_p = 0
                    for nv in adj[v]:
                        if nv == par[v] and check_p == 0:
                            check_p += 1
                            continue
                        elif order[nv] != -1:
                            low[v] = min(low[v], order[nv])
                        else:
                            par[nv] = v
                            st.append(nv)
                    continue
                v = ~v
                p = par[v]
                low[p] = min(low[p], low[v])
        self.order = order
        self.low = low
        self.roots = [i for i,v in enumerate(seen) if v]
        self.children = children

    def get_articulation(self) -> list[int]:
        order, low, roots, children = self.order, self.low, self.roots, self.children
        res = [0] * self.n
        for v in range(self.n):
            if v in roots:
                if len(children[v]) >= 2:
                    res[v] = 1
                continue
            for u in children[v]:
                if order[v] <= low[u]:
                    res[v] = 1
                    break
        return res
    
    def get_bridge(self) -> list[tuple[int,int]]:
        order, low, roots, children = self.order, self.low, self.roots, self.children
        res = []
        for v in roots:
            st = [v]
            while st:
                v = st.pop()
                for u in children[v]:
                    if order[v] < low[u]:
                        res.append((v,u))
                    st.append(u)
        return res
    

    def two_edge_connected_components(self) ->  tuple[list[int], list[tuple[int,int]]]:
        order, low, roots, children = self.order, self.low, self.roots, self.children
        
        components = [-1] * self.n
        new_edges = []
        idx = 0
        for v in roots:
            components[v] = idx
            st = [v]
            while st:
                v = st.pop()
                for u in children[v]:
                    if order[v] < low[u]:
                        idx += 1
                        components[u] = idx
                        new_edges.append((components[v], idx))
                    else:
                        components[u] = components[v]
                    st.append(u)
            idx += 1
        return components, new_edges

from heapq import *
INF = 10**18
def dijkstra(g, s, n):
    dist = [INF]*n
    hq = [(0, s)]
    dist[s] = 0
    while hq:
        d, v = heappop(hq)
        if dist[v]!=d:
            continue
        for to, c in g[v]:
            if dist[v] + c < dist[to]:
                dist[to] = dist[v] + c
                heappush(hq, (dist[to], to))
    return dist

n, m, s, t = na()
s -= 1
t -= 1
g = [[] for i in range(n)]

dic = dict()
gg = [[] for i in range(n)]
for i in range(m):
    a, b = na()
    a -= 1
    b -= 1
    g[a].append((b, i))
    g[b].append((a, i))
    gg[a].append(b)
    gg[b].append(a)
    dic[(a, b)] = i
    dic[(b, a)] = i


LL = LowLink(gg)

f = [0] * m
for x, y in LL.get_bridge():
    f[dic[(x, y)]] = 1    

BIG = 10 ** 9
G = [[] for i in range(n)]
for x in range(n):
    for y, i in g[x]:
        if f[i] == 0:
            G[x].append((y, BIG - 1))
        else:
            G[x].append((y, BIG))
# print(dist)
dist = dijkstra(G, s, n)
# print(dist)
# print(f)
res = dist[t]
if res == INF:
    print(-1)
else:

# print(dist)

    print((-res) % BIG)
0