2492. Minimum Score of a Path Between Two Cities

#php #leetcode #algorithms #programming

Difficulty: Medium

Topics: Staff, Depth-First Search, Breadth-First Search, Union-Find, Graph Theory, Weekly Contest 322

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] = [aᵢ, bᵢ, distanceᵢ] indicates that there is a bidirectional road between cities aᵢ and bᵢ with a distance equal to distanceᵢ. 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.

Example 3:

Input: n = 3, roads = [[1,2,3],[2,3,1],[1,3,2]]
Output: 1

Example 4:

Input: n = 5, roads = [[1,2,10],[2,3,5],[3,4,8],[4,5,3]]
Output: 3

Example 5:

Input: n = 6, roads = [[1,2,15],[2,3,12],[3,4,20],[4,6,8],[1,5,6],[5,6,10]]
Output: 6

Example 6:

Input: n = 4, roads = [[1,2,5],[2,4,3],[3,1,8]]
Output: 3

Constraints:

2 <= n <= 10⁵
1 <= roads.length <= 10⁵
roads[i].length == 3
1 <= aᵢ, bᵢ <= n
aᵢ != bᵢ
1 <= distancei <= 10⁴
There are no repeated edges.
There is at least one path between 1 and n.

Hint:

Can you solve the problem if the whole graph is connected?
Notice that if the graph is connected, you can always use any edge of the graph in your path.
How to solve the general problem in a similar way? Remove all the nodes that are not connected to 1 and n, then apply the previous solution in the new graph.

Solution:

We have designed an efficient solution to find the minimum possible score of a path between cities 1 and n. The key insight is that since we can traverse roads multiple times and revisit cities, the minimum score along any path from city 1 to city n is simply the minimum edge weight among all edges that are reachable from city 1 in the connected component containing city 1. This works because we can always detour through any reachable edge and return to our path, effectively including that edge's weight in our path's score.

Approach

Graph Connectivity Insight: Since we can reuse roads and revisit cities, any edge that is reachable from city 1 can be included in a path from city 1 to city n (as long as city n is also reachable from city 1).
DFS Traversal: We perform a Depth-First Search starting from city 1 to traverse the entire connected component containing city 1.
Score Tracking: While traversing, we track the minimum edge weight encountered in the connected component. This minimum value represents the answer.
Reachability Guarantee: The problem guarantees at least one path exists between city 1 and city n, so city n is in the same connected component as city 1.
Edge Case Handling: The solution works regardless of whether the graph is connected or not, as we only traverse the component containing city 1.

Let's implement this solution in PHP: 2492. Minimum Score of a Path Between Two Cities

<?php
/**
 * @param Integer $n
 * @param Integer[][] $roads
 * @return Integer
 */
function minScore(int $n, array $roads): int
{
    ...
    ...
    ...
    /**
     * go to ./solution.php
     */
}

// Test cases
echo minScore(4, [[1,2,9],[2,3,6],[2,4,5],[1,4,7]]) .  "\n";                                // Output: 5
echo minScore(4, [[1,2,2],[1,3,4],[3,4,7]]) .  "\n";                                        // Output: 2
echo minScore(3, [[1,2,3],[2,3,1],[1,3,2]]) .  "\n";                                        // Output: 1
echo minScore(5, [[1,2,10],[2,3,5],[3,4,8],[4,5,3]]) .  "\n";                               // Output: 3
echo minScore(6, [[1,2,15],[2,3,12],[3,4,20],[4,6,8],[1,5,6],[5,6,10]]) .  "\n";            // Output: 6
echo minScore(4, [[1,2,5],[2,4,3],[3,1,8]]) .  "\n";                                        // Output: 3

Explanation:

Why BFS/DFS works: We use DFS (or BFS) to visit all nodes in the connected component containing city 1. For each edge we traverse, we update our minimum score.
Why revisiting edges helps: The ability to traverse edges multiple times means we can go from city 1 to any reachable edge, traverse it, and return to continue our path to city n. This allows all reachable edges to contribute to the path's minimum score.
Example 1 Walkthrough: In the first example, DFS from node 1 visits nodes 2 and 4, encountering edges with weights 9, 5, and 7. The minimum among reachable edges is 5, which matches the output.
Example 3 Walkthrough: Starting from node 1, we visit nodes 2 and 3, encountering edges [1,2,2], [1,3,4], and [3,4,7]. The minimum is 2. Even though node 2 might seem like a dead end, we can go 1→2→1→3→4, incorporating the edge of weight 2 into our path.
Optimization: We don't need to check both directions of bidirectional edges separately since our adjacency list already accounts for both directions.

Complexity Analysis

Time Complexity: O(n + m), where n is the number of cities and m is the number of roads. Each node is visited at most once, and each edge is processed twice (once from each endpoint).
Space Complexity: O(n + m) for storing the adjacency list and O(n) for the visited array, resulting in O(n + m) total space.
Optimality: The solution is optimal as we must at least read all edges reachable from city 1 to find the minimum, which requires O(n + m) time in the worst case.

Contact Links

If you found this series helpful, please consider giving the repository a star on GitHub or sharing the post on your favorite social networks 😍. Your support would mean a lot to me!