Leetcode 2492: Minimum Score of a Path Between Two Cities
You are given a set of cities, each connected by bidirectional roads. Each road has a distance, and the score of a path between two cities is defined as the minimum distance of any road on that path. The task is to find the minimum score of a path between city 1 and city n. You are allowed to visit the cities multiple times, and the roads may be repeated.
Problem
Approach
Steps
Complexity
Input: The input consists of an integer n representing the number of cities, and a 2D array roads, where each road is represented as [ai, bi, distancei] meaning there is a bidirectional road between city ai and bi with distance distancei.
Example: n = 4, roads = [[1,2,9],[2,3,6],[2,4,5],[1,4,7]]
Constraints:
• 2 <= n <= 10^5
• 1 <= roads.length <= 10^5
• 1 <= ai, bi <= n
• 1 <= distancei <= 10^4
• There are no repeated edges.
• There is at least one path between city 1 and city n.
Output: Return the minimum possible score of a path between city 1 and city n. If no path exists, return -1.
Example: Output: 5
Constraints:
• The score is calculated by considering the minimum distance in the path between city 1 and city n.
Goal: The goal is to find the minimum score of a path between cities 1 and n by traversing the graph of cities and roads.
Steps:
• 1. Construct an adjacency list for the graph.
• 2. Use BFS or DFS starting from city 1 to visit all connected cities.
• 3. Track the minimum distance of any road encountered during traversal.
• 4. Return the minimum score of the path when city n is reached.
Goal: Ensure that all roads are bidirectional, and the graph is connected between city 1 and city n.
Steps:
• The graph is guaranteed to be connected between cities 1 and n.
• No duplicate roads exist in the input.
Assumptions:
• The input graph is connected for cities 1 and n.
• The roads form a connected graph between cities, ensuring that there is at least one path between city 1 and city n.
• Input: Input: n = 4, roads = [[1,2,9],[2,3,6],[2,4,5],[1,4,7]]
• Explanation: The cities can be connected through the path 1 -> 2 -> 4 with the minimum score being min(9,5), which is 5.
• Input: Input: n = 4, roads = [[1,2,2],[1,3,4],[3,4,7]]
• Explanation: The minimum score of the path from city 1 to city 4 is 2, which is the minimum distance encountered in the path 1 -> 2 -> 1 -> 3 -> 4.
Approach: To solve this problem, the approach uses breadth-first search (BFS) or depth-first search (DFS) to explore all the possible paths between cities, ensuring that the minimum road distance along the path is tracked.
Observations:
• The problem involves a pathfinding task with the additional requirement to track the minimum score of the roads on the path.
• By using BFS or DFS, we can efficiently explore the graph while keeping track of the minimum distance encountered on the path.
Steps:
• 1. Construct the adjacency list from the roads array.
• 2. Initialize a visited array to keep track of visited cities.
• 3. Use BFS or DFS starting from city 1 to traverse the roads.
• 4. Track the minimum distance encountered during traversal, updating the result if a lower value is found.
• 5. Return the minimum score of the path once city n is reached.
Empty Inputs:
• The input will always contain valid roads between cities and will not be empty.
Large Inputs:
• For large inputs, the algorithm should handle up to 100,000 cities and roads efficiently using BFS or DFS.
Special Values:
• The distances of the roads range between 1 and 10,000, ensuring no edge cases involving extreme values.
Constraints:
• Ensure BFS/DFS is implemented with efficient traversal to handle large inputs.
int minScore(int n, vector<vector<int>>& roads) {
vector<vector<vector<int>>> grid(n + 1);
for(auto it: roads) {
grid[it[0]].push_back({it[1], it[2]});
grid[it[1]].push_back({it[0], it[2]});
}
vector<int> vis(n + 1, false);
queue<int> q;
q.push(1);
vis[1] = true;
int mn = INT_MAX;
while(!q.empty()) {
int sz = q.size();
while(sz--) {
auto it = q.front();
q.pop();
for(auto x: grid[it]) {
mn = min(mn, x[1]);
if(!vis[x[0]]) {
q.push(x[0]);
vis[x[0]] = true;
}
}
}
}
return mn;
}
1 : Function Declaration
int minScore(int n, vector<vector<int>>& roads) {
This line declares the function `minScore` which takes in two parameters: `n` (number of nodes) and `roads` (a 2D vector representing the roads between nodes). It returns an integer representing the minimum score.
2 : Grid Initialization
vector<vector<vector<int>>> grid(n + 1);
A 3D vector `grid` is initialized to store the adjacency list representation of the graph. The `n + 1` ensures that node indexing starts from 1.
3 : Edge Addition
for(auto it: roads) {
This loop iterates through each road in the `roads` vector and updates the adjacency list (`grid`) for both directions of the road.
4 : Adjacency List Update
grid[it[0]].push_back({it[1], it[2]});
For each road, this line adds the edge from node `it[0]` to node `it[1]` with the corresponding score `it[2]`.
5 : Adjacency List Update
grid[it[1]].push_back({it[0], it[2]});
This line ensures the adjacency list is updated in both directions, so the graph is undirected.
6 : Visited Nodes Initialization
vector<int> vis(n + 1, false);
A vector `vis` of size `n + 1` is initialized to keep track of visited nodes. Initially, all nodes are set to `false`.
7 : Queue Initialization
queue<int> q;
A queue `q` is initialized to facilitate BFS traversal of the graph.
8 : Start BFS
q.push(1);
Node 1 is pushed onto the queue to start the BFS traversal.
9 : Mark Start Node as Visited
vis[1] = true;
Mark node 1 as visited.
10 : Minimum Score Initialization
int mn = INT_MAX;
The variable `mn` is initialized to `INT_MAX` to track the minimum score during the BFS traversal.
11 : BFS Loop Start
while(!q.empty()) {
This while loop runs as long as the queue is not empty, processing each node in the BFS.
12 : Queue Size Calculation
int sz = q.size();
The size of the queue is stored in `sz` to control the number of nodes to be processed in the current BFS level.
13 : Inner Loop
while(sz--) {
This inner loop processes each node at the current level of the BFS.
14 : Queue Front
auto it = q.front();
The front element of the queue is retrieved and stored in `it`, representing the current node to process.
15 : Queue Pop
q.pop();
The front element is removed from the queue after processing.
16 : Adjacency List Traversal
for(auto x: grid[it]) {
This loop iterates over all neighbors of the current node `it` by accessing the adjacency list `grid[it]`.
17 : Minimum Score Update
mn = min(mn, x[1]);
The minimum score is updated by comparing the current minimum with the score of the edge `x[1]`.
18 : Node Visit Check
if(!vis[x[0]]) {
If the neighboring node `x[0]` has not been visited, it is added to the BFS queue.
19 : Queue Push
q.push(x[0]);
The neighboring node `x[0]` is pushed to the queue for future processing.
20 : Mark Node as Visited
vis[x[0]] = true;
Mark the neighboring node `x[0]` as visited.
21 : Return Minimum Score
return mn;
The function returns the minimum score found during the BFS traversal.
Best Case: O(n + m)
Average Case: O(n + m)
Worst Case: O(n + m)
Description: The time complexity is O(n + m) where n is the number of cities and m is the number of roads, as each city and road is visited at most once during traversal.
Best Case: O(n)
Worst Case: O(n + m)
Description: The space complexity is O(n + m) due to the adjacency list and visited array. This accounts for the number of cities and roads.
| LeetCode Solutions Library / DSA Sheets / Course Catalog |
|---|
comments powered by Disqus