2492. Minimum Score of a Path Between Two Cities LeetCode Solution
In this guide, you will get 2492. Minimum Score of a Path Between Two Cities LeetCode Solution with the best time and space complexity. The solution to Minimum Score of a Path Between Two Cities problem is provided in various programming languages like C++, Java, and Python. This will be helpful for you if you are preparing for placements, hackathons, interviews, or practice purposes. The solutions provided here are very easy to follow and include detailed explanations.
Problem Statement of Minimum Score of a Path Between Two Cities
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.
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.
Complexity Analysis
Time Complexity: O(|V| + |E|)
Space Complexity: O(|V| + |E|)
2492. Minimum Score of a Path Between Two Cities LeetCode Solution in C++
class Solution {
public:
int minScore(int n, vector<vector<int>>& roads) {
int ans = INT_MAX;
vector<vector<pair<int, int>>> graph(n); // graph[u] := [(v, distance)]
queue<int> q{{0}};
vector<bool> seen(n);
seen[0] = true;
for (const vector<int>& r : roads) {
const int u = r[0] - 1;
const int v = r[1] - 1;
const int distance = r[2];
graph[u].emplace_back(v, distance);
graph[v].emplace_back(u, distance);
}
while (!q.empty()) {
const int u = q.front();
q.pop();
for (const auto& [v, d] : graph[u]) {
ans = min(ans, d);
if (seen[v])
continue;
q.push(v);
seen[v] = true;
}
}
return ans;
}
}; /* code provided by PROGIEZ */
2492. Minimum Score of a Path Between Two Cities LeetCode Solution in Java
class Solution {
public int minScore(int n, int[][] roads) {
int ans = Integer.MAX_VALUE;
List<Pair<Integer, Integer>>[] graph = new List[n]; // graph[u] := [(v, distance)]
Queue<Integer> q = new ArrayDeque<>(List.of(0));
boolean[] seen = new boolean[n];
seen[0] = true;
for (int i = 0; i < n; ++i)
graph[i] = new ArrayList<>();
for (final int[] r : roads) {
final int u = r[0] - 1;
final int v = r[1] - 1;
final int distance = r[2];
graph[u].add(new Pair<>(v, distance));
graph[v].add(new Pair<>(u, distance));
}
while (!q.isEmpty()) {
final int u = q.poll();
for (Pair<Integer, Integer> pair : graph[u]) {
final int v = pair.getKey();
final int d = pair.getValue();
ans = Math.min(ans, d);
if (seen[v])
continue;
q.offer(v);
seen[v] = true;
}
}
return ans;
}
} // code provided by PROGIEZ
2492. Minimum Score of a Path Between Two Cities LeetCode Solution in Python
class Solution:
def minScore(self, n: int, roads: list[list[int]]) -> int:
ans = math.inf
graph = [[] for _ in range(n + 1)] # graph[u] := [(v, distance)]
q = collections.deque([1])
seen = {1}
for u, v, distance in roads:
graph[u].append((v, distance))
graph[v].append((u, distance))
while q:
u = q.popleft()
for v, d in graph[u]:
ans = min(ans, d)
if v in seen:
continue
q.append(v)
seen.add(v)
return ans # code by PROGIEZ
