Problem

You are given a positive integer n which is the number of nodes of a 0-indexed directed weighted graph and a 0-indexed 2D array edges where edges[i] = [ui, vi, wi] indicates that there is an edge from node ui to node vi with weight wi.

You are also given a node s and a node array marked; your task is to find the minimum distance from s to any of the nodes in marked.

Return an integer denoting the minimum distance froms to any node inmarked or-1 if there are no paths from s to any of the marked nodes.

Examples

Example 1:

1
2
3
4
5
6

Input: n = 4, edges = [[0,1,1],[1,2,3],[2,3,2],[0,3,4]], s = 0, marked = [2,3]
Output: 4
Explanation: There is one path from node 0 (the green node) to node 2 (a red node), which is 0->1->2, and has a distance of 1 + 3 = 4.
There are two paths from node 0 to node 3 (a red node), which are 0->1->2->3 and 0->3, the first one has a distance of 1 + 3 + 2 = 6 and the second one has a distance of 4.
The minimum of them is 4.
![](https://fastly.jsdelivr.net/gh/doocs/leetcode@main/solution/2700-2799/2737.Find%20the%20Closest%20Marked%20Node/images/image_2023-06-13_16-34-38.png)

Example 2:

1
2
3
4
5
6

Input: n = 5, edges = [[0,1,2],[0,2,4],[1,3,1],[2,3,3],[3,4,2]], s = 1, marked = [0,4]
Output: 3
Explanation: There are no paths from node 1 (the green node) to node 0 (a red node).
There is one path from node 1 to node 4 (a red node), which is 1->3->4, and has a distance of 1 + 2 = 3.
So the answer is 3.
![](https://fastly.jsdelivr.net/gh/doocs/leetcode@main/solution/2700-2799/2737.Find%20the%20Closest%20Marked%20Node/images/image_2023-06-13_16-35-13.png)

Example 3:

1
2
3
4

Input: n = 4, edges = [[0,1,1],[1,2,3],[2,3,2]], s = 3, marked = [0,1]
Output: -1
Explanation: There are no paths from node 3 (the green node) to any of the marked nodes (the red nodes), so the answer is -1.
![](https://fastly.jsdelivr.net/gh/doocs/leetcode@main/solution/2700-2799/2737.Find%20the%20Closest%20Marked%20Node/images/image_2023-06-13_16-35-47.png)

Constraints:

  • 2 <= n <= 500
  • 1 <= edges.length <= 10^4
  • edges[i].length = 3
  • 0 <= edges[i][0], edges[i][1] <= n - 1
  • 1 <= edges[i][2] <= 10^6
  • 1 <= marked.length <= n - 1
  • 0 <= s, marked[i] <= n - 1
  • s != marked[i]
  • marked[i] != marked[j] for every i != j
  • The graph might have repeated edges.
  • The graph is generated such that it has no self-loops.

Solution

Method 1 – Dijkstra’s Algorithm (Shortest Path)

Intuition

We need the shortest path from the source node s to any node in the marked set. Dijkstra’s algorithm is ideal for finding the shortest path in a weighted directed graph with non-negative weights.

Approach

  1. Build an adjacency list from the edge list.
  2. Use Dijkstra’s algorithm starting from node s to compute the shortest distance to all nodes.
  3. For each node in marked, check its distance from s.
  4. Return the minimum distance among all marked nodes, or -1 if none are reachable.

Code

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24

class Solution {
public:
    int findClosestMarkedNode(int n, vector<vector<int>>& edges, int s, vector<int>& marked) {
        vector<vector<pair<int, int>>> g(n);
        for (auto& e : edges) g[e[0]].emplace_back(e[1], e[2]);
        vector<long long> dist(n, LLONG_MAX);
        priority_queue<pair<long long, int>, vector<pair<long long, int>>, greater<>> pq;
        dist[s] = 0;
        pq.emplace(0, s);
        while (!pq.empty()) {
            auto [d, u] = pq.top(); pq.pop();
            if (d > dist[u]) continue;
            for (auto& [v, w] : g[u]) {
                if (dist[v] > d + w) {
                    dist[v] = d + w;
                    pq.emplace(dist[v], v);
                }
            }
        }
        long long ans = LLONG_MAX;
        for (int v : marked) ans = min(ans, dist[v]);
        return ans == LLONG_MAX ? -1 : (int)ans;
    }
};
 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29

func findClosestMarkedNode(n int, edges [][]int, s int, marked []int) int {
    g := make([][]struct{to, w int}, n)
    for _, e := range edges {
        g[e[0]] = append(g[e[0]], struct{to, w int}{e[1], e[2]})
    }
    dist := make([]int, n)
    for i := range dist { dist[i] = 1<<60 }
    dist[s] = 0
    pq := &heapInt{{0, s}}
    heap.Init(pq)
    for pq.Len() > 0 {
        d, u := (*pq)[0][0], (*pq)[0][1]
        heap.Pop(pq)
        if d > dist[u] { continue }
        for _, e := range g[u] {
            if dist[e.to] > d+e.w {
                dist[e.to] = d + e.w
                heap.Push(pq, [2]int{dist[e.to], e.to})
            }
        }
    }
    ans := 1<<60
    for _, v := range marked {
        if dist[v] < ans { ans = dist[v] }
    }
    if ans == 1<<60 { return -1 }
    return ans
}
// heapInt implements heap.Interface for [2]int
 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27

class Solution {
    public int findClosestMarkedNode(int n, int[][] edges, int s, int[] marked) {
        List<int[]>[] g = new List[n];
        for (int i = 0; i < n; ++i) g[i] = new ArrayList<>();
        for (int[] e : edges) g[e[0]].add(new int[]{e[1], e[2]});
        long[] dist = new long[n];
        Arrays.fill(dist, Long.MAX_VALUE);
        PriorityQueue<long[]> pq = new PriorityQueue<>(Comparator.comparingLong(a -> a[0]));
        dist[s] = 0;
        pq.offer(new long[]{0, s});
        while (!pq.isEmpty()) {
            long[] top = pq.poll();
            long d = top[0]; int u = (int)top[1];
            if (d > dist[u]) continue;
            for (int[] e : g[u]) {
                int v = e[0], w = e[1];
                if (dist[v] > d + w) {
                    dist[v] = d + w;
                    pq.offer(new long[]{dist[v], v});
                }
            }
        }
        long ans = Long.MAX_VALUE;
        for (int v : marked) ans = Math.min(ans, dist[v]);
        return ans == Long.MAX_VALUE ? -1 : (int)ans;
    }
}
 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
16
17
18
19
20
21
22
23

class Solution {
    fun findClosestMarkedNode(n: Int, edges: Array<IntArray>, s: Int, marked: IntArray): Int {
        val g = Array(n) { mutableListOf<Pair<Int, Int>>() }
        for (e in edges) g[e[0]].add(e[1] to e[2])
        val dist = LongArray(n) { Long.MAX_VALUE }
        val pq = java.util.PriorityQueue(compareBy<Pair<Long, Int>> { it.first })
        dist[s] = 0L
        pq.add(0L to s)
        while (pq.isNotEmpty()) {
            val (d, u) = pq.poll()
            if (d > dist[u]) continue
            for ((v, w) in g[u]) {
                if (dist[v] > d + w) {
                    dist[v] = d + w
                    pq.add(dist[v] to v)
                }
            }
        }
        var ans = Long.MAX_VALUE
        for (v in marked) ans = minOf(ans, dist[v])
        return if (ans == Long.MAX_VALUE) -1 else ans.toInt()
    }
}
 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
16
17
18

import heapq
class Solution:
    def findClosestMarkedNode(self, n: int, edges: list[list[int]], s: int, marked: list[int]) -> int:
        g = [[] for _ in range(n)]
        for u, v, w in edges:
            g[u].append((v, w))
        dist = [float('inf')] * n
        dist[s] = 0
        h = [(0, s)]
        while h:
            d, u = heapq.heappop(h)
            if d > dist[u]: continue
            for v, w in g[u]:
                if dist[v] > d + w:
                    dist[v] = d + w
                    heapq.heappush(h, (dist[v], v))
        ans = min((dist[v] for v in marked), default=float('inf'))
        return -1 if ans == float('inf') else ans
 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29

use std::collections::BinaryHeap;
use std::cmp::Reverse;
impl Solution {
    pub fn find_closest_marked_node(n: i32, edges: Vec<Vec<i32>>, s: i32, marked: Vec<i32>) -> i32 {
        let n = n as usize;
        let mut g = vec![vec![]; n];
        for e in &edges {
            g[e[0] as usize].push((e[1] as usize, e[2] as i64));
        }
        let mut dist = vec![i64::MAX; n];
        let mut heap = BinaryHeap::new();
        dist[s as usize] = 0;
        heap.push(Reverse((0, s as usize)));
        while let Some(Reverse((d, u))) = heap.pop() {
            if d > dist[u] { continue; }
            for &(v, w) in &g[u] {
                if dist[v] > d + w {
                    dist[v] = d + w;
                    heap.push(Reverse((dist[v], v)));
                }
            }
        }
        let mut ans = i64::MAX;
        for &v in &marked {
            ans = ans.min(dist[v as usize]);
        }
        if ans == i64::MAX { -1 } else { ans as i32 }
    }
}
 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
16
17
18
19
20
21
22
23

class Solution {
    findClosestMarkedNode(n: number, edges: number[][], s: number, marked: number[]): number {
        const g: [number, number][][] = Array.from({length: n}, () => []);
        for (const [u, v, w] of edges) g[u].push([v, w]);
        const dist = Array(n).fill(Infinity);
        dist[s] = 0;
        const h: [number, number][] = [[0, s]];
        while (h.length) {
            h.sort((a, b) => a[0] - b[0]);
            const [d, u] = h.shift()!;
            if (d > dist[u]) continue;
            for (const [v, w] of g[u]) {
                if (dist[v] > d + w) {
                    dist[v] = d + w;
                    h.push([dist[v], v]);
                }
            }
        }
        let ans = Infinity;
        for (const v of marked) ans = Math.min(ans, dist[v]);
        return ans === Infinity ? -1 : ans;
    }
}

Complexity

  • ⏰ Time complexity: O((n + m) log n), where n is the number of nodes and m is the number of edges, due to Dijkstra’s algorithm.
  • 🧺 Space complexity: O(n + m), for the adjacency list and distance array.