2492. Minimum Score of a Path Between Two Cities - Explanation

1. Depth First Search

Intuition

The problem asks for the minimum edge weight on any path from city 1 to city n, where we can revisit edges and nodes. The key realization is that since we can traverse any edge multiple times, we're essentially looking for the minimum edge weight in the entire connected component containing city 1. If an edge is reachable from city 1, we can always include it in our path by going there and back.

Algorithm

Build an adjacency list from the edges, storing both the neighbor and the edge distance.
Initialize res to infinity and a visited set.
Run DFS starting from node 1:
- Mark the current node as visited.
- For each neighbor, update res with the minimum of res and the edge distance.
- Recursively visit unvisited neighbors.
Return res after DFS completes.

class Solution:
    def minScore(self, n: int, roads: list[list[int]]) -> int:
        adj = defaultdict(list)
        for src, dst, dist in roads:
            adj[src].append((dst, dist))
            adj[dst].append((src, dist))

        res = float("inf")
        visit = set()

        def dfs(node):
            nonlocal res
            if node in visit:
                return
            visit.add(node)
            for nei, dist in adj[node]:
                res = min(res, dist)
                dfs(nei)

        dfs(1)
        return res

Time & Space Complexity

Time complexity: $O(V + E)$
Space complexity: $O(V + E)$

Where $V$ is the number of vertices and $E$ is the number of edges.

2. Breadth First Search

Intuition

BFS achieves the same goal as DFS by exploring all reachable nodes level by level. Since we need to find the minimum edge weight in the connected component containing node 1, BFS works equally well. We process each node, check all its edges, and track the smallest weight seen.

Algorithm

Build an adjacency list storing neighbors and distances.
Initialize res to infinity, a visited array, and a queue starting with node 1.
While the queue is not empty:
- Dequeue a node.
- For each neighbor, update res with the minimum edge distance.
- If the neighbor hasn't been visited, mark it visited and enqueue it.
Return res.

class Solution:
    def minScore(self, n: int, roads: list[list[int]]) -> int:
        adj = [[] for _ in range(n + 1)]
        for src, dst, dist in roads:
            adj[src].append((dst, dist))
            adj[dst].append((src, dist))

        res = float("inf")
        visit = [False] * (n + 1)
        q = deque([1])
        visit[1] = True

        while q:
            node = q.popleft()
            for nei, dist in adj[node]:
                res = min(res, dist)
                if not visit[nei]:
                    visit[nei] = True
                    q.append(nei)

        return res

Time & Space Complexity

Time complexity: $O(V + E)$
Space complexity: $O(V + E)$

Where $V$ is the number of vertices and $E$ is the number of edges.

3. Iterative DFS

Intuition

This is the same approach as recursive DFS, but using an explicit stack instead of the call stack. This avoids potential stack overflow issues for very deep graphs and gives us more control over the traversal.

Algorithm

Build an adjacency list from the edges.
Initialize res to infinity, a visited array, and a stack with node 1.
While the stack is not empty:
- Pop a node from the stack.
- For each neighbor, update res with the minimum edge distance.
- If the neighbor hasn't been visited, mark it visited and push it onto the stack.
Return res.

class Solution:
    def minScore(self, n: int, roads: list[list[int]]) -> int:
        adj = [[] for _ in range(n + 1)]
        for src, dst, dist in roads:
            adj[src].append((dst, dist))
            adj[dst].append((src, dist))

        res = float("inf")
        visit = [False] * (n + 1)
        stack = [1]
        visit[1] = True

        while stack:
            node = stack.pop()
            for nei, dist in adj[node]:
                res = min(res, dist)
                if not visit[nei]:
                    visit[nei] = True
                    stack.append(nei)

        return res

Time & Space Complexity

Time complexity: $O(V + E)$
Space complexity: $O(V + E)$

Where $V$ is the number of vertices and $E$ is the number of edges.

4. Disjoint Set Union

Intuition

Union-Find provides another way to identify which edges belong to the same connected component as node 1. First, we union all nodes connected by edges. Then, we iterate through all edges and check if they belong to the same component as node 1. The minimum weight among those edges is our answer.

Algorithm

Initialize a DSU (Disjoint Set Union) structure with path compression and union by size.
For each edge, union the two endpoints.
Find the root of node 1.
Iterate through all edges:
- If either endpoint has the same root as node 1, update res with the minimum edge weight.
Return res.

class DSU:
    def __init__(self, n):
        self.Parent = list(range(n + 1))
        self.Size = [1] * (n + 1)

    def find(self, node):
        if self.Parent[node] != node:
            self.Parent[node] = self.find(self.Parent[node])
        return self.Parent[node]

    def union(self, u, v):
        pu, pv = self.find(u), self.find(v)
        if pu == pv:
            return False
        if self.Size[pu] >= self.Size[pv]:
            self.Size[pu] += self.Size[pv]
            self.Parent[pv] = pu
        else:
            self.Size[pv] += self.Size[pu]
            self.Parent[pu] = pv
        return True

class Solution:
    def minScore(self, n: int, roads: list[list[int]]) -> int:
        dsu = DSU(n)
        for src, dst, _ in roads:
            dsu.union(src, dst)

        res = float("inf")
        root = dsu.find(1)
        for src, dst, dist in roads:
            if dsu.find(src) == root:
                res = min(res, dist)

        return res

Time & Space Complexity

Time complexity: $O(V + (E * α(V)))$
Space complexity: $O(V)$

Where $V$ is the number of vertices and $E$ is the number of edges in the graph. $α()$ is used for amortized complexity.

Common Pitfalls

Treating It as a Shortest Path Problem

Many people instinctively reach for Dijkstra's algorithm when they see "minimum" and "path" in the same problem. However, this problem asks for the minimum edge weight along any path, not the shortest total distance. Since you can revisit edges freely, you simply need to find the smallest edge weight in the entire connected component containing node 1.

Only Considering Direct Paths

Some solutions only examine edges that lie on simple paths from node 1 to node n. This misses the key insight that you can traverse any edge in the connected component by taking detours. The answer is the minimum weight among all edges reachable from node 1, regardless of whether they appear on a direct path to node n.

Forgetting to Build Bidirectional Edges

The graph is undirected, so each edge must be added in both directions when constructing the adjacency list. Failing to do this will cause your traversal to miss large portions of the graph, leading to incorrect results when the minimum edge is only reachable through a path that requires traversing an edge in the "reverse" direction.