Choose a Shortest Path That Avoids Bob
Problem statement
Alice and Bob move simultaneously along one edge per second in an undirected, unweighted graph. Alice must choose a shortest path from her start to the destination. Bob may choose any walk to catch her.
Return whether Alice can choose a shortest path such that Bob cannot occupy the same node at the same or an earlier time at any step, including the destination. Bob's earliest arrival time therefore determines safety.
Function
canAliceReachSafely(n: int, edges: int[][], aliceStart: int, bobStart: int, destination: int) → booleanExamples
Example 1
n = 5edges = [[0,1],[1,4],[0,2],[2,3],[3,4]]aliceStart = 0bobStart = 3destination = 4return = falseAlice takes 0-1-4; Bob reaches the destination too late.
Example 2
n = 4edges = [[0,1],[1,3],[2,1]]aliceStart = 0bobStart = 2destination = 3return = falseBob reaches the shared middle node before Alice.
Example 3
n = 3edges = [[0,1],[1,2]]aliceStart = 0bobStart = 0destination = 2return = falseBob starts on Alice, so capture is immediate.
Constraints
1 <= n <= 100000.0 <= edges.length <= 200000.