Skip to content

2492. Minimum Score of a Path Between Two Cities

SourceWeekly Contest 322 Q3DifficultyMediumRating1679

Description

You are given a positive integer n representing n cities numbered from 1 to n. You are also given a 2D array roads where roads[i] = [ai, bi, distancei] indicates that there is a bidirectional road between cities ai and bi with a distance equal to distancei. The cities graph is not necessarily connected.

The score of a path between two cities is defined as the minimum distance of a road in this path.

Return the minimum possible score of a path between cities 1 and n.

Note:

  • A path is a sequence of roads between two cities.
  • It is allowed for a path to contain the same road multiple times, and you can visit cities 1 and n multiple times along the path.
  • The test cases are generated such that there is at least one path between 1 and n.

 

Example 1:

Input: n = 4, roads = [[1,2,9],[2,3,6],[2,4,5],[1,4,7]]
Output: 5
Explanation: The path from city 1 to 4 with the minimum score is: 1 -> 2 -> 4. The score of this path is min(9,5) = 5.
It can be shown that no other path has less score.

Example 2:

Input: n = 4, roads = [[1,2,2],[1,3,4],[3,4,7]]
Output: 2
Explanation: The path from city 1 to 4 with the minimum score is: 1 -> 2 -> 1 -> 3 -> 4. The score of this path is min(2,2,4,7) = 2.

 

Constraints:

  • 2 <= n <= 105
  • 1 <= roads.length <= 105
  • roads[i].length == 3
  • 1 <= ai, bi <= n
  • ai != bi
  • 1 <= distancei <= 104
  • There are no repeated edges.
  • There is at least one path between 1 and n.

Solutions

Solution 1: DFS

Thinking

Edges may be reused and \(1\) is connected to \(n\). A path's score is its lightest edge, and any \(1\)– \(n\) walk can reach every edge of that component, so the answer is the minimum weight in the component of \(1\).

DFS from \(1\), updating the answer on every edge.

According to the problem description, each edge can be traversed multiple times, and it is guaranteed that node \(1\) and node \(n\) are in the same connected component. Therefore, the problem is actually asking for the minimum edge weight in the connected component containing node \(1\).

We first build an undirected graph \(g\) from \(\textit{roads}\), then perform DFS starting from node \(1\). While traversing the connected component, we update the answer with \(\textit{ans} = \min(\textit{ans}, w)\) for each edge visited.

The time complexity is \(O(n + m)\), and the space complexity is \(O(n + m)\), where \(n\) and \(m\) are the number of nodes and edges, respectively.

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
16
17
18
class Solution:
    def minScore(self, n: int, roads: List[List[int]]) -> int:
        def dfs(a: int):
            vis[a] = True
            nonlocal ans
            for b, w in g[a]:
                ans = min(ans, w)
                if not vis[b]:
                    dfs(b)

        g = [[] for _ in range(n + 1)]
        for a, b, w in roads:
            g[a].append((b, w))
            g[b].append((a, w))
        ans = inf
        vis = [False] * (n + 1)
        dfs(1)
        return 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
30
31
32
33
class Solution {
    private int ans;
    private boolean[] vis;
    private List<int[]>[] g;

    public int minScore(int n, int[][] roads) {
        g = new ArrayList[n + 1];
        Arrays.setAll(g, k -> new ArrayList<>());

        for (int[] e : roads) {
            int a = e[0], b = e[1], w = e[2];
            g[a].add(new int[] {b, w});
            g[b].add(new int[] {a, w});
        }

        ans = Integer.MAX_VALUE;
        vis = new boolean[n + 1];

        dfs(1);
        return ans;
    }

    private void dfs(int a) {
        vis[a] = true;
        for (int[] nb : g[a]) {
            int b = nb[0], w = nb[1];
            ans = Math.min(ans, w);
            if (!vis[b]) {
                dfs(b);
            }
        }
    }
}

 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 minScore(int n, vector<vector<int>>& roads) {
        vector<vector<pair<int, int>>> g(n + 1);
        for (auto& e : roads) {
            int a = e[0], b = e[1], w = e[2];
            g[a].push_back({b, w});
            g[b].push_back({a, w});
        }

        vector<bool> vis(n + 1, false);
        int ans = INT_MAX;

        auto dfs = [&](this auto&& dfs, int a) -> void {
            vis[a] = true;
            for (auto& [b, w] : g[a]) {
                ans = min(ans, w);
                if (!vis[b]) {
                    dfs(b);
                }
            }
        };

        dfs(1);
        return 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
func minScore(n int, roads [][]int) int {
    g := make([][][2]int, n+1)
    for _, e := range roads {
        a, b, w := e[0], e[1], e[2]
        g[a] = append(g[a], [2]int{b, w})
        g[b] = append(g[b], [2]int{a, w})
    }

    vis := make([]bool, n+1)
    ans := int(1e9)

    var dfs func(int)
    dfs = func(a int) {
        vis[a] = true
        for _, nb := range g[a] {
            b, w := nb[0], nb[1]
            ans = min(ans, w)
            if !vis[b] {
                dfs(b)
            }
        }
    }

    dfs(1)
    return ans
}

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
function minScore(n: number, roads: number[][]): number {
    const g: [number, number][][] = Array.from({ length: n + 1 }, () => []);
    for (const [a, b, w] of roads) {
        g[a].push([b, w]);
        g[b].push([a, w]);
    }

    const vis = new Array(n + 1).fill(false);
    let ans = Infinity;

    const dfs = (a: number): void => {
        vis[a] = true;
        for (const [b, w] of g[a]) {
            ans = Math.min(ans, w);
            if (!vis[b]) {
                dfs(b);
            }
        }
    };

    dfs(1);
    return 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
30
31
impl Solution {
    pub fn min_score(n: i32, roads: Vec<Vec<i32>>) -> i32 {
        let n = n as usize;
        let mut g: Vec<Vec<(usize, i32)>> = vec![vec![]; n + 1];

        for e in roads {
            let a = e[0] as usize;
            let b = e[1] as usize;
            let w = e[2];
            g[a].push((b, w));
            g[b].push((a, w));
        }

        let mut vis = vec![false; n + 1];
        let mut ans = i32::MAX;

        fn dfs(a: usize, g: &Vec<Vec<(usize, i32)>>, vis: &mut Vec<bool>, ans: &mut i32) {
            vis[a] = true;

            for &(b, w) in &g[a] {
                *ans = (*ans).min(w);
                if !vis[b] {
                    dfs(b, g, vis, ans);
                }
            }
        }

        dfs(1, &g, &mut vis, &mut ans);
        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
/**
 * @param {number} n
 * @param {number[][]} roads
 * @return {number}
 */
var minScore = function (n, roads) {
    const g = Array.from({ length: n + 1 }, () => []);

    for (const [a, b, w] of roads) {
        g[a].push([b, w]);
        g[b].push([a, w]);
    }

    const vis = new Array(n + 1).fill(false);
    let ans = Infinity;

    const dfs = a => {
        vis[a] = true;
        for (const [b, w] of g[a]) {
            ans = Math.min(ans, w);
            if (!vis[b]) dfs(b);
        }
    };

    dfs(1);
    return ans;
};

Solution 2: BFS

Thinking

Method 1 walks the component of city \(1\) by recursion and keeps the minimum edge weight. A chain of roads uses a call depth equal to the node count. The same visited set also works with a queue and expands the component layer by layer.

We can also use BFS to solve this problem. Enqueue node \(1\) and expand the connected component layer by layer, updating the answer with \(\textit{ans} = \min(\textit{ans}, w)\) whenever an edge is visited.

The time complexity is \(O(n + m)\), and the space complexity is \(O(n + m)\), where \(n\) and \(m\) are the number of nodes and edges, respectively.

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
16
17
18
19
class Solution:
    def minScore(self, n: int, roads: List[List[int]]) -> int:
        g = [[] for _ in range(n + 1)]
        for a, b, w in roads:
            g[a].append((b, w))
            g[b].append((a, w))
        vis = [False] * (n + 1)
        vis[1] = True
        ans = inf
        q = deque([1])
        while q:
            for _ in range(len(q)):
                a = q.popleft()
                for b, w in g[a]:
                    ans = min(ans, w)
                    if not vis[b]:
                        vis[b] = True
                        q.append(b)
        return 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
30
31
32
33
class Solution {
    public int minScore(int n, int[][] roads) {
        List<int[]>[] g = new ArrayList[n + 1];
        Arrays.setAll(g, k -> new ArrayList<>());

        for (int[] e : roads) {
            int a = e[0], b = e[1], w = e[2];
            g[a].add(new int[] {b, w});
            g[b].add(new int[] {a, w});
        }

        boolean[] vis = new boolean[n + 1];
        Deque<Integer> q = new ArrayDeque<>();
        q.offer(1);
        vis[1] = true;
        int ans = Integer.MAX_VALUE;

        while (!q.isEmpty()) {
            for (int k = q.size(); k > 0; --k) {
                int a = q.pollFirst();
                for (int[] nb : g[a]) {
                    int b = nb[0], w = nb[1];
                    ans = Math.min(ans, w);
                    if (!vis[b]) {
                        vis[b] = true;
                        q.offer(b);
                    }
                }
            }
        }
        return 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
30
31
class Solution {
public:
    int minScore(int n, vector<vector<int>>& roads) {
        vector<vector<pair<int, int>>> g(n + 1);
        for (auto& e : roads) {
            int a = e[0], b = e[1], w = e[2];
            g[a].push_back({b, w});
            g[b].push_back({a, w});
        }

        vector<bool> vis(n + 1, false);
        int ans = INT_MAX;
        queue<int> q{{1}};
        vis[1] = true;

        while (!q.empty()) {
            for (int k = q.size(); k; --k) {
                int a = q.front();
                q.pop();
                for (auto [b, w] : g[a]) {
                    ans = min(ans, w);
                    if (!vis[b]) {
                        vis[b] = true;
                        q.push(b);
                    }
                }
            }
        }
        return 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 minScore(n int, roads [][]int) int {
    g := make([][][2]int, n+1)
    for _, e := range roads {
        a, b, w := e[0], e[1], e[2]
        g[a] = append(g[a], [2]int{b, w})
        g[b] = append(g[b], [2]int{a, w})
    }

    vis := make([]bool, n+1)
    ans := int(1e9)
    q := []int{1}
    vis[1] = true

    for len(q) > 0 {
        for k := len(q); k > 0; k-- {
            a := q[0]
            q = q[1:]
            for _, nb := range g[a] {
                b, w := nb[0], nb[1]
                ans = min(ans, w)
                if !vis[b] {
                    vis[b] = true
                    q = append(q, b)
                }
            }
        }
    }
    return 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
function minScore(n: number, roads: number[][]): number {
    const g: [number, number][][] = Array.from({ length: n + 1 }, () => []);
    for (const [a, b, w] of roads) {
        g[a].push([b, w]);
        g[b].push([a, w]);
    }

    const vis = new Array(n + 1).fill(false);
    let ans = Infinity;
    let q: number[] = [1];
    vis[1] = true;

    while (q.length > 0) {
        const nq: number[] = [];
        for (const a of q) {
            for (const [b, w] of g[a]) {
                ans = Math.min(ans, w);
                if (!vis[b]) {
                    vis[b] = true;
                    nq.push(b);
                }
            }
        }
        q = nq;
    }
    return 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
30
31
32
33
34
35
36
use std::collections::VecDeque;

impl Solution {
    pub fn min_score(n: i32, roads: Vec<Vec<i32>>) -> i32 {
        let n = n as usize;
        let mut g: Vec<Vec<(usize, i32)>> = vec![vec![]; n + 1];

        for e in roads {
            let a = e[0] as usize;
            let b = e[1] as usize;
            let w = e[2];
            g[a].push((b, w));
            g[b].push((a, w));
        }

        let mut vis = vec![false; n + 1];
        let mut ans = i32::MAX;
        let mut q = VecDeque::new();
        q.push_back(1);
        vis[1] = true;

        while !q.is_empty() {
            for _ in 0..q.len() {
                let a = q.pop_front().unwrap();
                for &(b, w) in &g[a] {
                    ans = ans.min(w);
                    if !vis[b] {
                        vis[b] = true;
                        q.push_back(b);
                    }
                }
            }
        }
        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
30
31
32
33
/**
 * @param {number} n
 * @param {number[][]} roads
 * @return {number}
 */
var minScore = function (n, roads) {
    const g = Array.from({ length: n + 1 }, () => []);

    for (const [a, b, w] of roads) {
        g[a].push([b, w]);
        g[b].push([a, w]);
    }

    const vis = new Array(n + 1).fill(false);
    let ans = Infinity;
    let q = [1];
    vis[1] = true;

    while (q.length > 0) {
        const nq = [];
        for (const a of q) {
            for (const [b, w] of g[a]) {
                ans = Math.min(ans, w);
                if (!vis[b]) {
                    vis[b] = true;
                    nq.push(b);
                }
            }
        }
        q = nq;
    }
    return ans;
};

Solution 3: Explicit Stack

Thinking

Edges may be reused and \(1\) is connected to \(n\). A path's score is its lightest edge, and any \(1\)–\(n\) walk can reach every edge of that component, so the answer is the minimum weight in the component of \(1\). With \(n \le 10^5\), recursing through that component is too deep: a chain makes the call depth \(n\).

An explicit stack starts at \(1\). When a city is popped and still unvisited, every incident edge updates the minimum and unvisited neighbors are pushed.

According to the problem description, each edge can be traversed multiple times, and it is guaranteed that node \(1\) and node \(n\) are in the same connected component. Therefore, the problem is actually asking for the minimum edge weight in the connected component containing node \(1\).

We first build an undirected graph \(g\) from \(\textit{roads}\), then walk from node \(1\) with an explicit stack. When a node is popped, we update the answer with \(\textit{ans} = \min(\textit{ans}, w)\) for each of its edges and push its unvisited neighbors.

The time complexity is \(O(n + m)\), and the space complexity is \(O(n + m)\), where \(n\) and \(m\) are the number of nodes and edges, respectively.

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
16
17
18
19
class Solution:
    def minScore(self, n: int, roads: List[List[int]]) -> int:
        g = [[] for _ in range(n + 1)]
        for a, b, w in roads:
            g[a].append((b, w))
            g[b].append((a, w))
        ans = inf
        vis = [False] * (n + 1)
        stk = [1]
        while stk:
            a = stk.pop()
            if vis[a]:
                continue
            vis[a] = True
            for b, w in g[a]:
                ans = min(ans, w)
                if not vis[b]:
                    stk.append(b)
        return 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
30
class Solution {
    public int minScore(int n, int[][] roads) {
        List<int[]>[] g = new List[n + 1];
        Arrays.setAll(g, k -> new ArrayList<>());
        for (int[] e : roads) {
            int a = e[0], b = e[1], w = e[2];
            g[a].add(new int[] {b, w});
            g[b].add(new int[] {a, w});
        }
        int ans = Integer.MAX_VALUE;
        boolean[] vis = new boolean[n + 1];
        Deque<Integer> stk = new ArrayDeque<>();
        stk.push(1);
        while (!stk.isEmpty()) {
            int a = stk.pop();
            if (vis[a]) {
                continue;
            }
            vis[a] = true;
            for (int[] nb : g[a]) {
                int b = nb[0], w = nb[1];
                ans = Math.min(ans, w);
                if (!vis[b]) {
                    stk.push(b);
                }
            }
        }
        return 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
class Solution {
public:
    int minScore(int n, vector<vector<int>>& roads) {
        vector<vector<pair<int, int>>> g(n + 1);
        for (auto& e : roads) {
            int a = e[0], b = e[1], w = e[2];
            g[a].push_back({b, w});
            g[b].push_back({a, w});
        }
        vector<char> vis(n + 1);
        int ans = INT_MAX;
        vector<int> stk{1};
        while (!stk.empty()) {
            int a = stk.back();
            stk.pop_back();
            if (vis[a]) {
                continue;
            }
            vis[a] = 1;
            for (auto& [b, w] : g[a]) {
                ans = min(ans, w);
                if (!vis[b]) {
                    stk.push_back(b);
                }
            }
        }
        return 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
func minScore(n int, roads [][]int) int {
    g := make([][][2]int, n+1)
    for _, e := range roads {
        a, b, w := e[0], e[1], e[2]
        g[a] = append(g[a], [2]int{b, w})
        g[b] = append(g[b], [2]int{a, w})
    }
    vis := make([]bool, n+1)
    ans := int(1e9)
    stk := []int{1}
    for len(stk) > 0 {
        a := stk[len(stk)-1]
        stk = stk[:len(stk)-1]
        if vis[a] {
            continue
        }
        vis[a] = true
        for _, nb := range g[a] {
            b, w := nb[0], nb[1]
            ans = min(ans, w)
            if !vis[b] {
                stk = append(stk, b)
            }
        }
    }
    return 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
function minScore(n: number, roads: number[][]): number {
    const g: [number, number][][] = Array.from({ length: n + 1 }, () => []);
    for (const [a, b, w] of roads) {
        g[a].push([b, w]);
        g[b].push([a, w]);
    }
    const vis = new Array(n + 1).fill(false);
    let ans = Infinity;
    const stk: number[] = [1];
    while (stk.length) {
        const a = stk.pop()!;
        if (vis[a]) {
            continue;
        }
        vis[a] = true;
        for (const [b, w] of g[a]) {
            ans = Math.min(ans, w);
            if (!vis[b]) {
                stk.push(b);
            }
        }
    }
    return 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
impl Solution {
    pub fn min_score(n: i32, roads: Vec<Vec<i32>>) -> i32 {
        let n = n as usize;
        let mut g: Vec<Vec<(usize, i32)>> = vec![vec![]; n + 1];
        for e in roads {
            let a = e[0] as usize;
            let b = e[1] as usize;
            let w = e[2];
            g[a].push((b, w));
            g[b].push((a, w));
        }
        let mut vis = vec![false; n + 1];
        let mut ans = i32::MAX;
        let mut stk = vec![1usize];
        while let Some(a) = stk.pop() {
            if vis[a] {
                continue;
            }
            vis[a] = true;
            for &(b, w) in &g[a] {
                ans = ans.min(w);
                if !vis[b] {
                    stk.push(b);
                }
            }
        }
        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
/**
 * @param {number} n
 * @param {number[][]} roads
 * @return {number}
 */
var minScore = function (n, roads) {
    const g = Array.from({ length: n + 1 }, () => []);
    for (const [a, b, w] of roads) {
        g[a].push([b, w]);
        g[b].push([a, w]);
    }
    const vis = new Array(n + 1).fill(false);
    let ans = Infinity;
    const stk = [1];
    while (stk.length) {
        const a = stk.pop();
        if (vis[a]) {
            continue;
        }
        vis[a] = true;
        for (const [b, w] of g[a]) {
            ans = Math.min(ans, w);
            if (!vis[b]) {
                stk.push(b);
            }
        }
    }
    return ans;
};

Comments