Graph Traversal Coding Problem

HardPython

Problem

TikTok Trust and Safety services route security events through directed processing nodes. Each connection has a positive latency, and an incident may use at most one emergency firewall bypass that reduces the latency of one connection to floor(latency / 2).

Given the graph, source, and destination, return the minimum possible total latency. The bypass may be unused, and each connection can be traversed at most as part of the selected route. Return -1 if the destination is unreachable.

Formal Specification

Implement shortest_route_with_bypass(n, edges, source, destination).

n is an integer number of nodes labeled 0 through n - 1.
edges is a list of directed triples [u, v, latency].
source and destination are integer node labels.
Return an integer representing the minimum latency, or -1 when no route exists.

Treat each node as having two states: the bypass is unused or already used. A route cannot use the bypass more than once.

Constraints

1 <= n <= 10^5
0 <= len(edges) <= 2 * 10^5
0 <= u, v < n and u != v
1 <= latency <= 10^9
Parallel directed edges may exist.
All latencies are positive.

Function Signature

def shortest_route_with_bypass(n, edges, source, destination):

Formal Specification

Implement shortest_route_with_bypass(n, edges, source, destination).

n is an integer number of nodes labeled 0 through n - 1.
edges is a list of directed triples [u, v, latency].
source and destination are integer node labels.
Return an integer representing the minimum latency, or -1 when no route exists.

Treat each node as having two states: the bypass is unused or already used. A route cannot use the bypass more than once.