Overview

This problem requires computing the shortest distance from the wild dog base \(P\) to each location, then solving the so-called maximum bottleneck path problem: among all simple paths from \(S\) to \(T\), maximize the “minimum \(d\) value of all locations on the path (= safety level).”

Analysis

Meaning of Safety Level

The safety level is “the distance from the wild dogs to the location on the path that is closest to the wild dogs.” Since we want to maximize this, we need to find a path that passes through only locations as far from the wild dogs as possible.

Reduction to Bottleneck Path Problem

Each location \(v\) has a weight \(d(v)\) (shortest distance from \(P\)), and we want to maximize the minimum vertex weight on an \(S\)-\(T\) path. This is a variant of the classic problem known as the “maximum bottleneck path.”

Naive Approach (Binary Search)

One could consider binary searching on the decision problem “does a path with safety level \(\geq x\) exist?” However, since \(d\) values can be as large as \(O(N \times 10^9)\) and there are many distinct values, coordinate compression would be needed for binary search, making it somewhat cumbersome.

Efficient Approach: Descending Order Addition + Union-Find

We use the following key observation:

Add all locations in decreasing order of \(d\) value, and each time a location is added, connect it with already-added adjacent vertices using Union-Find. The \(d\) value of the vertex being added at the moment \(S\) and \(T\) first become connected is the answer.

Why this is correct: Adding vertices in decreasing order of \(d\) value corresponds to “gradually lowering the safety threshold.” The maximum \(x\) such that \(S\) and \(T\) are connected using only vertices with \(d\) value \(\geq x\) is the desired answer. The \(d\) value of the vertex at the moment \(S\) and \(T\) first become connected during descending-order addition is exactly that \(x\).

Algorithm

1. Use Dijkstra’s algorithm to compute the shortest distance \(d(v)\) from location \(P\) to all locations.
2. Sort all locations in descending order of \(d\) value (vertices with \(d = +\infty\) come first).
3. Prepare a Union-Find structure and add vertices in sorted order. When adding a vertex, union it with already-added adjacent vertices.
4. The \(d\) value at the moment \(S\) and \(T\) belong to the same connected component is the answer.
   • If that \(d\) value is \(+\infty\), output INF.
   • Otherwise, output that value.

Concrete Example

Consider 4 locations with \(S=1, T=4, P=2\). If the \(d\) values are \(d(1)=5, d(2)=0, d(3)=10, d(4)=3\), then adding in descending order gives the sequence \(3 \to 1 \to 4 \to 2\). If \(S\) and \(T\) become connected at the point when \(1\) and \(4\) have been added, the answer is \(\min(d(1), d(4)) = 3\) (the \(d\) value at the moment of connection).

Complexity

• Time complexity: \(O((N + M) \log N)\)
  • Dijkstra’s algorithm: \(O((N + M) \log N)\)
  • Sorting: \(O(N \log N)\)
  • Union-Find operations: \(O(M \cdot \alpha(N))\) (essentially \(O(M)\))
• Space complexity: \(O(N + M)\)

Implementation Notes

• Handling \(+\infty\): In Python, float('inf') can be used, which naturally allows placing vertices with \(d = +\infty\) at the front when sorting.

• Union-Find with path compression: Since the number of vertices and edges can be up to \(2 \times 10^5\), path compression and union by rank are used for speedup.

• Added flag: An added[v] array manages whether a vertex has already been added, ensuring we do not union with unadded adjacent vertices.

• Cases where \(P = S\) or \(P = T\): Since \(d(P) = 0\), the safety level becomes \(0\) or less (i.e., \(0\)), but the algorithm automatically handles this correctly.

  Source Code

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

---

This editorial was generated by claude4.6opus-thinking.