Overview

Compute the shortest distance \(d(X)\) from the wild dog base \(P\) to each point, then check whether it’s possible to travel from \(S\) to \(T\) using only points that are far from the base (i.e., have large \(d(X)\)). This maximizes “the minimum distance to the base among all points on the path.”

Analysis

Key Insight 1: We are NOT evaluating “path length”

The safety we want to find is $\(\min(d(v_0), d(v_1), \ldots, d(v_k))\)\( and NOT the travel time from \)S \to T\( (sum of edge weights). In other words, this is a problem about "avoiding points close to the wild dog base," where each vertex has a score \)d(v)$ (larger means safer).

Key Insight 2: The simple path condition doesn’t actually matter

In an undirected graph, if \(S\) can reach \(T\), then even if there are cycles along the way, we can remove them to obtain a path that doesn’t visit the same vertex more than once (a simple path).
Therefore, it suffices to determine “reachability.”

Why a naive approach is difficult

• Directly searching for “the simple path with maximum safety” is impossible because the number of paths can be exponential.
• One could assume safety \(X\), check “can we go from \(S\) to \(T\) using only vertices with \(d(v)\ge X\)” via BFS/DFS each time, and binary search on \(X\)… but performing the check many times is expensive (with some effort it can be done in \(O((N+M)\log N)\), but there’s a more direct solution).

Solution: Connectivity viewed through a threshold is monotone

A path with safety at least \(X\) exists ⇔
\(S\) and \(T\) are connected in the “subgraph consisting only of vertices satisfying \(d(v)\ge X\).”

As \(X\) decreases, more vertices remain and connectivity becomes easier to achieve (monotonicity).
So, we “activate” vertices in decreasing order of \(d(v)\), and the moment \(S\) and \(T\) first become connected, the corresponding \(d\) value is the answer.

Also, if \(S \to T\) is connected using only vertices with \(d(v)=+\infty\) (unreachable from \(P\)), then the safety is \(+\infty\), so we output INF.

Algorithm

1. Use Dijkstra’s algorithm to compute the shortest distance \(d(v)\) from base \(P\) to all vertices.

   • Edge weights \(W_i\) are only used here.
   • Unreachable vertices have \(d(v)=+\infty\).

2. Sort vertices in decreasing order of \(d(v)\) (\(+\infty\) comes first).

3. Prepare a Union-Find (DSU) and activate vertices one by one in decreasing order.

   • When activating vertex \(u\), for each adjacent vertex \(v\) that is already active, perform union(u, v) in the DSU.
   • At each step, if both \(S\) and \(T\) are active and find(S)==find(T), then \(d(u)\) at that point is the maximum safety. Terminate here.

4. Output:

   • If the answer is \(+\infty\), output INF
   • Otherwise, output that integer value

Intuitive Image
Start with a graph consisting only of “safe (large \(d\)) points,” and gradually add more dangerous points. At some point, \(S\) and \(T\) become connected for the first time. That “boundary” represents the limit of how high the safety can be.

Complexity

• Time complexity: \(O((N+M)\log N)\)
  • Dijkstra’s algorithm: \(O((N+M)\log N)\)
  • Vertex sorting: \(O(N\log N)\)
  • DSU merges: each edge is examined at most once, so \(O(M\alpha(N))\) (nearly linear)
• Space complexity: \(O(N+M)\) (adjacency list, distance array, DSU, etc.)

Implementation Notes

• Handling INF: Vertices unreachable by Dijkstra are assigned a huge distance value (\(10^{30}\) in the code), ensuring they are processed first during sorting. If \(S\) and \(T\) become connected at this stage, the answer is INF.

• Optimizations:

  • Since the input size can be up to \(2\times 10^5\), fast input using sys.stdin.buffer.read() is employed.
  • The adjacency list uses a compressed representation with array (head/to/wt/nxt) instead of Python’s list of lists, improving memory usage and speed.

• Why the simple path condition can be ignored: If two vertices are connected, a simple path between them always exists, so checking reachability alone gives the correct answer.

  Source Code

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()

---

This editorial was generated by gpt-5.2-high.