Nearest Flagged Node

Medium

You are given a directed graph with n nodes numbered 0 to n - 1. Each edge edges[i] = [u, v, w] goes from u to v with weight w; the same pair of nodes may be joined by several edges. Some nodes carry a flag, and their numbers are listed in flagged. Find the length of the shortest path from node start to any flagged node. If no flagged node can be reached from start, return -1.

Example 1

n=4, edges=[[0, 1, 2], [1, 2, 2], [0, 3, 7], [2, 3, 1]], start=0, flagged=[3] → 5

The direct edge 0 → 3 weighs 7, but the path 0 → 1 → 2 → 3 costs only 2 + 2 + 1 = 5.

Example 2

n=3, edges=[[1, 0, 4]], start=0, flagged=[1, 2] → -1

The only edge goes from 1 to 0, not the other way, so nothing can be reached from node 0.

Constraints

2 ≤ n ≤ 500
1 ≤ len(edges) ≤ 10⁴
edges[i] = [u, v, w], 0 ≤ u, v < n, u ≠ v
1 ≤ w ≤ 10⁶
1 ≤ len(flagged) ≤ n − 1
0 ≤ start, flagged[i] < n; all flagged[i] are distinct and differ from start

Have you seen this problem in a real interview?

Solved by0

Tried by0

Submissions0

Acceptance—

Topics

Graph Array Shortest Path Heap (Priority Queue)

Similar problems

Shortest Path of a Rolling Ball Medium Most Reliable Relay Route Medium Souvenir Round Trip Medium A Trip Through Tunnels Medium Stops That Close Medium

Input

n=4, edges=[[0, 1, 2], [1, 2, 2], [0, 3, 7], [2, 3, 1]], start=0, flagged=[3]

Expected

Run checks the first 3 tests in your browser. Submit checks all 74 tests on the server, hidden ones included.