2492

2492. Minimum Score of a Path Between Two Cities (Medium)

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.

Companies: Unbxd

Related Topics:
Depth-First Search, Breadth-First Search, Union Find, Graph

Similar Questions:

• Checking Existence of Edge Length Limited Paths (Hard)
• Checking Existence of Edge Length Limited Paths II (Hard)

Solution 1. DFS

// OJ: https://leetcode.com/problems/minimum-score-of-a-path-between-two-cities
// Author: github.com/lzl124631x
// Time: O(N + E)
// Space: O(N + E)
class Solution {
public:
    int minScore(int n, vector<vector<int>>& E) {
        vector<vector<pair<int, int>>> G(n);
        for (auto &e : E) {
            int u = e[0] - 1, v = e[1] - 1, dist = e[2];
            G[u].emplace_back(v, dist);
            G[v].emplace_back(u, dist);
        }
        vector<bool> seen(n);
        int ans = INT_MAX;
        function<void(int)> dfs = [&](int u) {
            if (seen[u]) return;
            seen[u] = true;
            for (auto &[v, dist] : G[u]) {
                ans = min(ans, dist);
                dfs(v);
            }
        };
        dfs(0);
        return ans;
    }
};

Solution 2. Union Find

// OJ: https://leetcode.com/problems/minimum-score-of-a-path-between-two-cities
// Author: github.com/lzl124631x
// Time: O(N + ElogN). This can be reduced to O(N + E) if we use union-by-rank.
// Space: O(N)
class Solution {
public:
    int minScore(int n, vector<vector<int>>& E) {
        vector<int> id(n), score(n, INT_MAX);
        iota(begin(id), end(id), 0);
        function<int(int)> find = [&](int a) {
            return id[a] == a ? a : (id[a] = find(id[a]));
        };
        auto connect = [&](int u, int v, int dist) {
            int p = find(u), q = find(v);
            id[q] = p;
            score[p] = min({score[p], score[q], dist});
        };
        for (auto &e : E) {
            int u = e[0] - 1, v = e[1] - 1, dist = e[2];
            connect(u, v, dist);
        }
        return score[find(0)];
    }
};