We use cookies (including Google cookies) to personalize ads and analyze traffic. By continuing to use our site, you accept our Privacy Policy.

SimplyLeet
TagsDisclaimersPrivacyTermsContactAbout Us

Minimum Score of a Path Between Two Cities

Difficulty: Medium

Problem 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.

Key Insights

  • The problem requires finding a path between two cities while minimizing the maximum weight of the edges in that path.
  • The path can revisit cities and edges multiple times.
  • A graph traversal algorithm (like BFS or DFS) can be utilized to explore all possible paths.

Space and Time Complexity

Time Complexity: O(V + E), where V is the number of vertices (cities) and E is the number of edges (roads). Each edge and vertex is processed at most once.
Space Complexity: O(V + E) for the adjacency list representation of the graph and the visited array.

Solution

To solve the problem, we can use a graph traversal algorithm such as Depth-First Search (DFS) or Breadth-First Search (BFS).

  1. Construct an undirected graph using an adjacency list from the given roads.
  2. Use BFS or DFS to traverse from city 1 to city n, while maintaining the minimum distance of any edge encountered along the way.
  3. The minimum distance found during the traversal will be the score of the path.

The algorithm focuses on exploring all paths and utilizing a priority data structure to keep track of the minimum road distance.

Code Solutions

from collections import defaultdict, deque

def minScore(n, roads):
    graph = defaultdict(list)
    
    # Build the graph
    for a, b, distance in roads:
        graph[a].append((b, distance))
        graph[b].append((a, distance))
    
    min_distance = float('inf')
    visited = set()
    
    # BFS to find the minimum score path
    queue = deque([1])
    visited.add(1)
    
    while queue:
        city = queue.popleft()
        
        # Explore neighbors
        for neighbor, distance in graph[city]:
            if neighbor not in visited:
                visited.add(neighbor)
                queue.append(neighbor)
            # Update the minimum distance encountered
            min_distance = min(min_distance, distance)
    
    return min_distance
← Back to All Questions