Find A Threshold-Limited Path With Minimum Required Safety

Problem Statement

You are designing a routing engine for a secure communications network with n servers numbered from 0 to n - 1. The network is represented as an undirected graph with bidirectional connections given by a 2D array edges, where edges[i] = [u, v, latency, safety_level] indicates a link between server u and server v with transmission delay latency and required safety clearance safety_level.

You are also given two server IDs, source and destination, and a threshold value max_latency.

Rules for valid paths:

1. A link can only be used if latency <= max_latency.
2. The safety clearance required for an entire path is defined as the maximum safety_level among all links traversed on that path.

Return the minimum required safety clearance to travel from source to destination. If source == destination, return 0. If no valid path exists, return -1.

Function Signature

def min_required_safety(n: int, edges: list[list[int]], source: int, destination: int, max_latency: int) -> int:
    pass

Input and Output Format

• Input:
  • n: integer representing the number of nodes (0 to n - 1).
  • edges: list of [u, v, latency, safety_level] integers.
  • source: starting node integer.
  • destination: target node integer.
  • max_latency: integer upper bound on an edge's latency.
• Output:
  • An integer representing the minimum required clearance, or -1 if unreachable.

Examples

Example 1

Input: 
n = 4
edges = [
    [0, 1, 10, 5],
    [1, 2, 8, 9],
    [0, 2, 15, 7],
    [2, 3, 5, 4]
]
source = 0
destination = 3
max_latency = 12

Output: 9

Explanation: The link (0, 2) has latency = 15 > 12, so it cannot be used. The only available path is 0 -> 1 -> 2 -> 3. The safety levels along this path are 5, 9, and 4. The path clearance requirement is max(5, 9, 4) = 9.

Example 2

Input: 
n = 3
edges = [
    [0, 1, 5, 8],
    [1, 2, 6, 7]
]
source = 0
destination = 2
max_latency = 4

Output: -1

Explanation: All available edges have latency greater than max_latency = 4. No path exists, so return -1.

Constraints

• 1 <= n <= 10^5
• 0 <= len(edges) <= 2 * 10^5
• edges[i] = [u, v, latency, safety_level] where 0 <= u, v < n and u != v
• 0 <= latency, safety_level, max_latency <= 10^9
• 0 <= source, destination < n
• There can be multiple edges between the same pair of vertices.