Minimum Score Of A Path Between Two Cities · Interview Problem

Back to problems

Leetcode

minimum-score-of-a-path-between-two-cities

Medium

Graphs

Union Find

Depth-First Search

Breadth-First Search

Minimum Score Of A Path Between Two Cities

Find the minimum score of a path between two cities in an undirected graph where scores on edges represent distances.

Acceptance 100%

Start Practice

Problem Statement

Core description from the backend problem record.

Description

You are given an integer n representing the number of cities numbered from 1 to n. You are also given a 2D array roads where each roads[i] = [ai, bi, distancei] indicates there is a bidirectional road between cities ai and bi with a distance equal to distancei. A path's score is defined as the minimum distance edge in the path. Your task is to find the minimum possible score of a path between city 1 and city n. A path is a sequence of cities connected by roads and may contain repeated cities or roads.

Input Format

An integer n representing the number of cities.
A 2D integer array roads where each roads[i] = [ai, bi, distancei].

Output Format

An integer representing the minimum score of a path between city 1 and city n.

Constraints

2 <= n <= 10^5
1 <= roads.length <= 10^5
roads[i].length == 3
1 <= ai, bi <= n
ai != bi
1 <= distancei <= 10^4
There is at least one path between city 1 and city n.

Loading Preptin

Description

Input Format

Output Format

Constraints