Approach
Breadth-first search
For Find the Closest Marked Node, the implementation explores reachable states in layers, which is the standard shape for unweighted shortest paths and minimum-step transitions.
- Model each valid configuration as a state and each legal move as an edge.
- Seed the queue with the starting state and mark it immediately.
- Expand each state once, recording distance or reachability for unseen neighbours.
Code notes
- 54 lines of Java from the credited upstream file 2737.java.
- The implementation visibly relies on sequence storage, work queue.
- 5 loop blocks detected.
Complexity
Verify that each state and transition is processed only a bounded number of times; that determines the traversal cost.
Check the problem constraints before deciding whether this complexity will pass.
Use this to learn the idea, then write your own version.
1class Solution {2 public int minimumDistance(int n, List<List<Integer>> edges, int s, int[] marked) {3 int ans = Integer.MAX_VALUE;4 List<Pair<Integer, Integer>>[] graph = new List[n];5 6 for (int i = 0; i < n; i++)7 graph[i] = new ArrayList<>();8 9 for (List<Integer> edge : edges) {10 final int u = edge.get(0);11 final int v = edge.get(1);12 final int w = edge.get(2);13 graph[u].add(new Pair<>(v, w));14 }15 16 int[] dist = dijkstra(graph, s);17 18 for (final int u : marked)19 ans = Math.min(ans, dist[u]);20 21 return ans == Integer.MAX_VALUE ? -1 : ans;22 }23 24 private int[] dijkstra(List<Pair<Integer, Integer>>[] graph, int src) {25 int[] dist = new int[graph.length];26 Arrays.fill(dist, Integer.MAX_VALUE);27 28 dist[src] = 0;29 Queue<Pair<Integer, Integer>> minHeap =30 new PriorityQueue<>(Comparator.comparingInt(Pair::getKey)) {31 {32 offer(new Pair<>(dist[src], src)); 33 }34 };35 36 while (!minHeap.isEmpty()) {37 final int d = minHeap.peek().getKey();38 final int u = minHeap.poll().getValue();39 if (d > dist[u])40 continue;41 for (Pair<Integer, Integer> pair : graph[u]) {42 final int v = pair.getKey();43 final int w = pair.getValue();44 if (d + w < dist[v]) {45 dist[v] = d + w;46 minHeap.offer(new Pair<>(dist[v], v));47 }48 }49 }50 51 return dist;52 }53}54