Minimum score of a path between two cities

Depth-First Search Breadth-First Search Union-Find Graph Theory

58.6% acceptance

Feb 25, 2026

1906

323

You are given n cities (1 to n) and roads[i] = [ai, bi, distancei] (bidirectional). The score of a path is the minimum road distance in the path. Return the minimum possible score of a path between cities 1 and n (can revisit edges). Since we can revisit, the answer is just the minimum edge weight in the connected component of 1 and n.

Solution

Rust

Time O(n * m)

Space O(n * m)

LeetCode

solution.rs

impl Solution {
  pub fn min_score(n: i32, roads: Vec<Vec<i32>>) -> i32 {
    let n = n as usize;
    let mut adj: Vec<Vec<(usize, i32)>> = vec![vec![]; n + 1];
    for r in &roads {
      let (a, b, d) = (r[0] as usize, r[1] as usize, r[2]);
      adj[a].push((b, d));
      adj[b].push((a, d));
    }
    let mut visited = vec![false; n + 1];
    let mut min_d = i32::MAX;
    let mut queue = std::collections::VecDeque::new();
    queue.push_back(1usize);
    visited[1] = true;
    while let Some(u) = queue.pop_front() {
      for &(v, d) in &adj[u] {
        min_d = min_d.min(d);
        if !visited[v] {
          visited[v] = true;
          queue.push_back(v);
        }
      }
    }
    min_d
  }
}