概要

野犬の拠点 \(P\) から各地点への最短距離 \(d(X)\) を求め、その値が大きい（=拠点から遠い）地点だけを通って \(S\) から \(T\) へ行けるかを調べることで、「経路上で最も拠点に近い地点の距離」を最大化します。

考察

重要な気づき 1：評価したいのは「経路の長さ」ではない

求めたい安全度は $\(\min(d(v_0), d(v_1), \ldots, d(v_k))\)\( であり、\)S \to T\( の移動時間（辺重みの和）ではありません。 つまり「野犬拠点に近い地点を踏まないようにする」問題で、各頂点にはスコア \)d(v)$（大きいほど安全）が付いているとみなせます。

重要な気づき 2：単純パス条件は実は気にしなくてよい

無向グラフで \(S\) から \(T\) へ到達可能なら、途中にサイクルがあっても削っていけば同じ頂点を2回以上通らない（単純な）パスにできます。
したがって「到達可能かどうか」を判定できれば十分です。

素朴解が難しい理由

• 「安全度最大の単純パス」を直接探すと、パス数は指数個になり探索は不可能です。
• 安全度を \(X\) と仮定して「\(d(v)\ge X\) の頂点だけで \(S\) から \(T\) に行けるか」を毎回 BFS/DFS で調べ、\(X\) を二分探索…という方法も考えられますが、判定を何度も行うのが重いです（工夫すれば \(O((N+M)\log N)\) にはできますが、より直接的に解けます）。

解決策：しきい値で見たときの「連結性」は単調

安全度が少なくとも \(X\) の経路が存在する ⇔
「\(d(v)\ge X\) を満たす頂点だけを残した部分グラフ」で \(S\) と \(T\) が連結。

\(X\) を下げるほど残る頂点が増え、連結になりやすくなります（単調性）。
そこで、\(d(v)\) が大きい頂点から順に「有効化」していき、初めて \(S\) と \(T\) が繋がった瞬間の \(d\) が答えになります。

また、\(d(v)=+\infty\)（\(P\) から到達不能）の頂点だけで \(S\to T\) が繋がるなら、安全度は \(+\infty\) なので INF を出力します。

アルゴリズム

1. ダイクストラ法で拠点 \(P\) から全頂点への最短距離 \(d(v)\) を求める

   • 辺重み \(W_i\) はここでのみ使います。
   • 到達不能な頂点は \(d(v)=+\infty\) とする。

2. 頂点を \(d(v)\) の 降順に並べる（\(+\infty\) が最初に来る）。

3. Union-Find（DSU）を用意し、頂点を降順に1つずつ「active（有効）」にする。

   • 頂点 \(u\) を有効化したら、隣接頂点 \(v\) がすでに有効なら DSU で union(u, v) する。
   • 各ステップで、\(S\) と \(T\) がともに有効かつ find(S)==find(T) になったら、その時の値 \(d(u)\) が最大安全度。そこで終了。

4. 出力：

   • 得られた答えが \(+\infty\) なら INF
   • そうでなければその整数値

直感的なイメージ
「安全な（\(d\) が大きい）地点だけで作るグラフ」から始め、だんだん危険な地点も追加していくと、ある時点で初めて \(S\) と \(T\) が繋がる。その“境目”が「どこまで安全度を上げられるか」の限界になります。

計算量

• 時間計算量: \(O((N+M)\log N)\)
  
  • ダイクストラ法: \(O((N+M)\log N)\)
    
  • 頂点ソート: \(O(N\log N)\)
    
  • DSU の統合: 全辺を高々1回見るので \(O(M\alpha(N))\)（ほぼ線形）
• 空間計算量: \(O(N+M)\)（隣接リスト、距離配列、DSU など）

実装のポイント

• INF の扱い：ダイクストラで到達不能な頂点は距離を巨大値（コードでは \(10^{30}\)）にし、ソートで先に処理されるようにします。\(S\) と \(T\) がその段階で繋がれば答えは INF です。

• 高速化：

  • 入力サイズが最大 \(2\times 10^5\) なので、sys.stdin.buffer.read() による高速入力を使っています。
  • 隣接リストは Python のリストのリストではなく、array による圧縮表現（head/to/wt/nxt）でメモリと速度を改善しています。

• 単純パス条件を無視してよい理由：連結なら必ず単純パスが存在するため、到達可能性だけ見れば正解になります。

  ソースコード

import sys
import heapq
from array import array

INF = 10**30

def main():
    data = sys.stdin.buffer.read()
    ndata = len(data)
    idx = 0

    def next_int():
        nonlocal idx
        while idx < ndata and data[idx] <= 32:
            idx += 1
        num = 0
        while idx < ndata and data[idx] > 32:
            num = num * 10 + (data[idx] - 48)
            idx += 1
        return num

    N = next_int()
    M = next_int()
    S = next_int()
    T = next_int()
    P = next_int()

    head = array('i', [-1]) * (N + 1)
    to = array('i')
    wt = array('q')
    nxt = array('i')

    def add_edge(u, v, w):
        to.append(v)
        wt.append(w)
        nxt.append(head[u])
        head[u] = len(to) - 1

    for _ in range(M):
        u = next_int()
        v = next_int()
        w = next_int()
        add_edge(u, v, w)
        add_edge(v, u, w)

    # Dijkstra from P to compute d(x)
    dist = [INF] * (N + 1)
    dist[P] = 0
    pq = [(0, P)]
    heappop = heapq.heappop
    heappush = heapq.heappush
    while pq:
        du, u = heappop(pq)
        if du != dist[u]:
            continue
        e = head[u]
        while e != -1:
            v = to[e]
            nd = du + wt[e]
            if nd < dist[v]:
                dist[v] = nd
                heappush(pq, (nd, v))
            e = nxt[e]

    order = sorted(range(1, N + 1), key=dist.__getitem__, reverse=True)

    parent = list(range(N + 1))
    size = [1] * (N + 1)

    def find(x):
        while parent[x] != x:
            parent[x] = parent[parent[x]]
            x = parent[x]
        return x

    def union(a, b):
        ra = find(a)
        rb = find(b)
        if ra == rb:
            return
        if size[ra] < size[rb]:
            ra, rb = rb, ra
        parent[rb] = ra
        size[ra] += size[rb]

    active = [False] * (N + 1)

    ans = None
    for u in order:
        active[u] = True
        e = head[u]
        while e != -1:
            v = to[e]
            if active[v]:
                union(u, v)
            e = nxt[e]
        if active[S] and active[T] and find(S) == find(T):
            ans = dist[u]
            break

    if ans is None:
        ans = 0  # should not happen due to constraints

    if ans >= INF // 2:
        sys.stdout.write("INF\n")
    else:
        sys.stdout.write(str(ans) + "\n")

if __name__ == "__main__":
    main()

---

この解説は gpt-5.2-high によって生成されました。