Problem Brief

Shortest Path with Mandatory Waypoint

FULLTIMEONSITE INTERVIEW

See Google online assessment and hiring insights

You are given a weighted graph with n nodes labeled 0 through n - 1. Each edge is represented as [u, v, w], meaning there is an edge between nodes u and v with non-negative distance w.

Compute two values:

the length of the shortest path from start to target
the length of the shortest path from start to target that must pass through waypoint

If a required path does not exist, use -1 for that entry.

Function Description

Complete the function shortestPathWithWaypoint in the editor below.

shortestPathWithWaypoint has the following parameters:

int n: the number of nodes
int[][] edges: undirected weighted edges [u, v, w]
int start: the starting node
int target: the destination node
int waypoint: the node that the constrained path must visit

Returns

int[]: a length-2 array [bestDistance, bestDistanceViaWaypoint].

1Example 1

Input

n = 5, edges = [[0, 1, 2], [1, 2, 3], [0, 3, 10], [2, 4, 1], [3, 4, 2], [1, 3, 2]], start = 0, target = 4, waypoint = 1

Output

[6, 6]

Explanation

The shortest path from 0 to 4 is 0 -> 1 -> 2 -> 4 with total cost 6. That path already passes through the mandatory waypoint 1, so both answers are 6.

2Example 2

Input

n = 4, edges = [[0, 1, 1], [1, 3, 1], [0, 2, 1]], start = 0, target = 3, waypoint = 2

Output

[2, -1]

Explanation

The unconstrained shortest path is 0 -> 1 -> 3 with cost 2. There is no path from 2 to 3, so no valid route can pass through the waypoint.

Constraints

Limits and guarantees your solution can rely on.

1 <= n <= 2 * 10^5
0 <= edges.length <= 3 * 10^5
0 <= w <= 10^9
All edge weights are non-negative.
If no path exists for a requested scenario, return -1 for that entry.