結果

問題 No.3463 Beltway
コンテスト
ユーザー LyricalMaestro
提出日時 2026-04-08 01:55:25
言語 PyPy3
(7.3.17)
コンパイル:
pypy3 -mpy_compile _filename_
実行:
pypy3 _filename_
結果
WA  
実行時間 -
コード長 1,964 bytes
記録
記録タグの例:
初AC ショートコード 純ショートコード 純主流ショートコード 最速実行時間
コンパイル時間 276 ms
コンパイル使用メモリ 85,700 KB
実行使用メモリ 197,688 KB
最終ジャッジ日時 2026-04-08 01:55:35
合計ジャッジ時間 6,724 ms
ジャッジサーバーID
（参考情報） 		judge3_0 / judge1_0
このコードへのチャレンジ
（要ログイン）
ファイルパターン 結果
sample AC * 1
other AC * 15 WA * 2
権限があれば一括ダウンロードができます

ソースコード

diff #
raw source code 

# https://yukicoder.me/problems/no/3463

from collections import deque
import heapq

MAX_INT = 10 ** 18

def main():
    V, E, S, G = map(int, input().split())
    ab = []
    for _ in range(E):
        a, b = map(int ,input().split())
        ab.append((a - 1 ,b - 1))

    # 次数1のグラフから徐々に削っていって残ったものだけ
    next_nodes = [{} for _ in range(V)]
    for i in range(E):
        a, b = ab[i]
        next_nodes[a][b] = i
        next_nodes[b][a] = i

    queue = deque()
    for i in range(V):
        if len(next_nodes[i]) == 1:
            queue.append(i)

    not_cycle = set()    
    while len(queue) > 0:
        v = queue.popleft()
        for w, edge_inex in next_nodes[v].items():
            del next_nodes[w][v]
            not_cycle.add(edge_inex)
            if len(next_nodes[w]) == 1:
                queue.append(w)
        
        next_nodes[v].clear()
    
    # ダイクストラ探索
    next_nodes = [[] for _ in range(V)]
    for i in range(E):
        a, b = ab[i]
        no_cycle_flg = 1 if i in not_cycle else 0
        next_nodes[a].append((b, no_cycle_flg))
        next_nodes[b].append((a, no_cycle_flg))

    queue = []
    fix = [MAX_INT ] * V
    seen = [MAX_INT] * V
    seen[0] = S - 1
    heapq.heappush(queue, (0, S- 1))
    while len(queue) > 0:
        cost, v = heapq.heappop(queue)
        if fix[v] < MAX_INT:
            continue

        fix[v] = cost
        for w, no_cycle_flg in next_nodes[v]:
            if fix[w] < MAX_INT:
                continue

            new_cost = E ** 2 + cost + no_cycle_flg
            if seen[w] > new_cost:
                seen[w] = new_cost
                heapq.heappush(queue, (new_cost, w))
    
    if fix[G - 1] == MAX_INT:
        print(-1)
    else:
        x = fix[G - 1]
        ans1 = x // (E ** 2)
        ans2 = x % (E ** 2)
        print(ans1 - ans2)

                
            





if __name__ == "__main__":
    main()
0