2492. Minimum Score of a Path Between Two Cities

MediumView on LeetCode

Depth-First Search Graph

Time: O(n + m)

Space: O(n + m)

Problem Overview

The graph is connected and undirected.

Intuition

The graph is connected and undirected. Any path from city 1 to city n can only use edges in the component reachable from 1. The minimum score of a path is limited by its weakest edge, so the answer is the minimum edge weight among all edges reachable from city 1.

Algorithm

1Build adjacency list from roads.
2DFS (or BFS) from city 1, marking visited cities.
3Whenever traversing an edge of weight w, update ans = min(ans, w).
4Return ans after visiting the whole reachable component.

Example Walkthrough

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

1.DFS from 1 visits edges with weights 4, 3, 2, and 1.
2.The smallest edge weight on any reachable edge is 1.

Output: 1

Common Pitfalls

•You do not need to find a specific 1→n path — every path uses only edges in the same connected component.
•Initialize ans to a large value and update on every edge relaxation during DFS.

2492.cs

// Approach: DFS from city 1 through the connected component. The answer is the minimum edge
// weight on any edge reachable from city 1 (any path 1→n uses only those edges).
// Time: O(n + m) Space: O(n + m)
public class Solution
{
    private int ans;
    private bool[] vis;
    private List<int[]>[] g;

    public int MinScore(int n, int[][] roads)
    {
        g = new List<int[]>[n + 1];
        for (int i = 0; i <= n; i++)
            g[i] = new List<int[]>();

        foreach (var e in roads)
        {
            int a = e[0], b = e[1], w = e[2];
            g[a].Add(new int[] { b, w });
            g[b].Add(new int[] { a, w });
        }

        ans = int.MaxValue;
        vis = new bool[n + 1];

        Dfs(1);
        return ans;
    }

    private void Dfs(int a)
    {
        vis[a] = true;
        foreach (var nb in g[a])
        {
            int b = nb[0], w = nb[1];
            ans = Math.Min(ans, w);
            if (!vis[b])
                Dfs(b);
        }
    }
}

Was this solution helpful?