Problem Statement in English

You’re given an integer n representing the number of cities in a country. The cities are numbered from 1 to n. You’re also given a 2D integer array roads, where $roads[i] = [a_i, b_i, distance_i]$ indicates that there is a bidirectional road between cities $a_i$ and $b_i$ with a distance equal to $distance_i$. The cities graph is not necessarily connected.

Approach

At the heart of this problem, it’s just asking us to find the lowest score that is possible to achieve on a path that passes through city 1 and city n. The fact that you can travel on a road multiple times means that sometimes the lowest score is not necessarily on the direct path from city 1 to city n. Instead, it could be on a path that goes beyond.

So we do a depth-first search (DFS) or breadth-first search (BFS) starting from city n and keep going until we can’t anymore. The question guarantees that there is a path between city 1 and city n. The minimum distance we encounter will be our answer.

And we’re done!

Solution in Python


class Solution:
    def minScore(self, n: int, roads: List[List[int]]) -> int:
        stack = [n]
        seen = set()
        res = inf

        adj = defaultdict(list)

        for a, b, d in roads:
            adj[a].append((b, d))
            adj[b].append((a, d))

        while stack:
            node = stack.pop()

            if node in seen: continue
            seen.add(node)

            for nei, d in adj[node]:
                if nei in seen: continue

                res = min(res, d)
                stack.append(nei)

        return res

Complexity

  • Time: $O(n + m)$
    You’re given n cities and m roads. We iterate over all the roads once to build the adjacency list, and then we perform a depth-first search (DFS) or breadth-first search (BFS) to traverse the graph, which takes $O(n + m)$ time.

  • Space: $O(n)$
    We use a stack to perform DFS, which can hold up to n cities in the worst case. Additionally, we use a set to keep track of seen cities, which also takes up to $O(n)$ space.

And we are done.