概要

野犬の拠点 \(P\) からの最短距離を各地点について求めた上で、\(S\) から \(T\) への単純パスのうち「経路上の全地点の \(d\) 値の最小値（＝安全度）」を最大化する、いわゆる 最大ボトルネックパス問題 を解く問題です。

考察

安全度の意味

安全度は「経路上で最も野犬に近い地点の、野犬からの距離」です。これを最大化したいので、なるべく野犬から遠い地点だけを通る経路を見つけたいということになります。

ボトルネックパス問題への帰着

各地点 \(v\) に重み \(d(v)\)（\(P\) からの最短距離）が付いていて、\(S\)-\(T\) パスにおける 頂点重みの最小値を最大化 したい問題です。これは「最大ボトルネックパス」と呼ばれる典型問題の一種です。

素朴なアプローチ（二分探索）

「安全度 \(\geq x\) のパスが存在するか？」を判定問題にして二分探索する方法が考えられます。しかし \(d\) の値が最大 \(O(N \times 10^9)\) 程度と大きく、値の種類も多いため、座標圧縮して二分探索する必要があり、やや面倒です。

効率的なアプローチ：降順追加 + Union-Find

以下の重要な観察を使います：

全地点を \(d\) 値の 大きい順 に追加していき、追加するたびに既に追加済みの隣接頂点と Union-Find で連結する。\(S\) と \(T\) が初めて連結になった瞬間の追加頂点の \(d\) 値が答え。

なぜ正しいか： \(d\) 値が大きい順に追加するということは、「安全度の閾値を徐々に下げていく」ことに対応します。閾値 \(x\) 以上の頂点だけを使って \(S\)-\(T\) が連結になる最大の \(x\) が求める答えです。降順に追加していって初めて \(S\)-\(T\) が繋がった瞬間の頂点の \(d\) 値がまさにその \(x\) です。

アルゴリズム

1. Dijkstra 法 で地点 \(P\) から全地点への最短距離 \(d(v)\) を求める。
2. 全地点を \(d\) 値の 降順 にソートする（\(d = +\infty\) の頂点が先頭）。
3. Union-Find を用意し、ソート順に頂点を追加する。追加時に、隣接する既追加頂点と union する。
4. \(S\) と \(T\) が同じ連結成分に入った瞬間の \(d\) 値が答え。
   • そのときの \(d\) 値が \(+\infty\) なら INF を出力。
   • そうでなければその値を出力。

具体例

地点が 4 つで \(S=1, T=4, P=2\) の場合を考えます。\(d\) 値が \(d(1)=5, d(2)=0, d(3)=10, d(4)=3\) だとすると、降順に追加すると \(3 \to 1 \to 4 \to 2\) の順です。\(1\) と \(4\) が追加された時点で \(S\)-\(T\) が繋がれば、答えは \(\min(d(1), d(4)) = 3\) となります（繋がるタイミングの \(d\) 値）。

計算量

• 時間計算量: \(O((N + M) \log N)\)
  • Dijkstra 法：\(O((N + M) \log N)\)
  • ソート：\(O(N \log N)\)
  • Union-Find の操作：\(O(M \cdot \alpha(N))\)（ほぼ \(O(M)\)）
• 空間計算量: \(O(N + M)\)

実装のポイント

• \(+\infty\) の扱い：Python では float('inf') を使えるため、ソート時に \(+\infty\) の頂点を先頭に配置する処理が自然に書けます。

• Union-Find の経路圧縮：頂点数・辺数が \(2 \times 10^5\) あるため、経路圧縮とランクによる併合を行い高速化します。

• 追加済みフラグ：added[v] 配列で、その頂点がすでに追加済みかを管理し、未追加の隣接頂点とは union しないようにします。

• \(P = S\) や \(P = T\) の場合：\(d(P) = 0\) なので安全度は \(0\) 以下（つまり \(0\)）になりますが、アルゴリズムが自動的に正しく処理します。

  ソースコード

import heapq
import sys
input = sys.stdin.readline

def solve():
    N, M = map(int, input().split())
    S, T, P = map(int, input().split())
    
    adj = [[] for _ in range(N + 1)]
    for _ in range(M):
        u, v, w = map(int, input().split())
        adj[u].append((v, w))
        adj[v].append((u, w))
    
    # Dijkstra from P to compute d(X) for all X
    INF = float('inf')
    dist = [INF] * (N + 1)
    dist[P] = 0
    pq = [(0, P)]
    while pq:
        d, u = heapq.heappop(pq)
        if d > dist[u]:
            continue
        for v, w in adj[u]:
            nd = d + w
            if nd < dist[v]:
                dist[v] = nd
                heapq.heappush(pq, (nd, v))
    
    # Now we want to find S-T simple path maximizing min(d(v) for v in path)
    # This is the "maximum bottleneck path" problem with bottleneck values d(v).
    
    # Binary search on the answer: can we find S-T path using only nodes with d(v) >= threshold?
    # But d values can be huge (up to ~2*10^14) or INF.
    
    # Better approach: maximum bottleneck path via maximum spanning tree
    # Node bottleneck: for each edge (u,v), the bottleneck value is min(d(u), d(v))
    # We want to find S-T path maximizing the minimum node value.
    # Equivalent to: build maximum spanning tree with edge weight = min(d(u), d(v)),
    # then the answer is the minimum edge weight on the S-T path in this MST.
    
    # But actually, we can use a simpler approach:
    # Sort all nodes by d value descending. Use union-find. Add nodes one by one
    # (in decreasing order of d). When adding a node, connect it to all its neighbors
    # that are already added. Check if S and T are connected. The answer is the d value
    # of the node that first connects S and T.
    
    # Special case: if d(S) = INF and d(T) = INF and there's a path using only INF nodes -> INF
    
    # Create list of (d[v], v) sorted descending
    nodes = []
    for i in range(1, N + 1):
        nodes.append((dist[i], i))
    
    # Sort descending by dist value. INF values first.
    # We need to handle INF carefully. Let's treat INF as a very large number.
    nodes.sort(key=lambda x: -x[0] if x[0] != INF else float('inf'))
    # Actually let's sort properly: INF nodes first, then by decreasing d
    nodes.sort(key=lambda x: (-1, -0) if x[0] == INF else (0, -x[0]))
    
    parent = list(range(N + 1))
    rank = [0] * (N + 1)
    added = [False] * (N + 1)
    
    def find(x):
        while parent[x] != x:
            parent[x] = parent[parent[x]]
            x = parent[x]
        return x
    
    def union(a, b):
        a, b = find(a), find(b)
        if a == b:
            return
        if rank[a] < rank[b]:
            a, b = b, a
        parent[b] = a
        if rank[a] == rank[b]:
            rank[a] += 1
    
    answer = None
    for d_val, v in nodes:
        added[v] = True
        for u, w in adj[v]:
            if added[u]:
                union(v, u)
        if added[S] and added[T] and find(S) == find(T):
            if d_val == INF:
                answer = "INF"
            else:
                answer = d_val
            break
    
    print(answer)

solve()

---

この解説は claude4.6opus-thinking によって生成されました。