Minimum Score of a Path Between Two Cities

Minimum Score of a Path Between Two Cities - Problem

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.

Note:

A path is a sequence of roads between two cities.
It is allowed for a path to contain the same road multiple times, and you can visit cities 1 and n multiple times along the path.
The test cases are generated such that there is at least one path between 1 and n.

Input & Output

Example 1 — Basic Path

$ Input: n = 4, roads = [[1,2,9],[2,3,6],[2,4,5],[1,4,7]]

› Output: 5

💡 Note: The path from city 1 to 4: 1 → 4 has minimum road distance 7. But we can go 1 → 2 → 4 with minimum road distance min(9,5) = 5, which is better.

Example 2 — Direct Connection

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

› Output: 2

💡 Note: Path 1 → 2 → 1 → 3 → 4 uses roads with distances [2,2,4,7], minimum is 2.

Constraints

2 ≤ n ≤ 10⁵
1 ≤ roads.length ≤ 10⁵
roads[i].length == 3
1 ≤ a_i, b_i ≤ n
a_i ≠ b_i
1 ≤ distance_i ≤ 10⁴

Visualization

Tap to expand

Understanding the Visualization

Input Graph

Cities connected by bidirectional roads with distances

Find Connected Component

Explore all roads reachable from city 1

Return Minimum

The minimum edge weight in the connected component

Key Takeaway

🎯 Key Insight: Since roads can be reused, we just need the minimum edge in the connected component containing both cities

Asked in

G Google 15 a Amazon 12 M Microsoft 8 f Facebook 6

The key insight is that since we can reuse roads multiple times, we just need to find the minimum edge weight in the connected component containing both cities 1 and n. Best approach uses DFS/BFS to explore the connected component. Time: O(V + E), Space: O(V + E)

Common Approaches

Approach	Time	Space	Notes
✓ DFS Exploration	O(V + E)	O(V + E)	Use DFS to explore all reachable roads from city 1 and find minimum distance
BFS Exploration	O(V + E)	O(V + E)	Use BFS to explore all reachable roads level by level and find minimum distance
Union-Find with Edge Sorting	O(E log E)	O(V)	Sort all edges by distance and use Union-Find to check connectivity

DFS Exploration — Algorithm Steps

Build adjacency list from roads
Start DFS from city 1
Track minimum road distance in connected component

Visualization

Tap to expand

Step-by-Step Walkthrough

Build Graph

Create adjacency list from roads

DFS Traversal

Visit all cities reachable from city 1

Track Minimum

Keep track of minimum road distance encountered

Code -

solution.c — C

#include <stdio.h>
#include <stdlib.h>
#include <string.h>
#include <limits.h>

typedef struct Edge {
    int to, dist;
    struct Edge* next;
} Edge;

typedef struct {
    Edge* head;
} AdjList;

int visited[100001];
int minScore;

void dfs(int city, AdjList* graph) {
    if (visited[city]) return;
    visited[city] = 1;
    
    Edge* edge = graph[city].head;
    while (edge) {
        if (edge->dist < minScore) {
            minScore = edge->dist;
        }
        dfs(edge->to, graph);
        edge = edge->next;
    }
}

int solution(int n, int roads[][3], int roadsSize) {
    AdjList graph[100001];
    for (int i = 0; i <= n; i++) {
        graph[i].head = NULL;
        visited[i] = 0;
    }
    
    minScore = INT_MAX;
    
    for (int i = 0; i < roadsSize; i++) {
        int a = roads[i][0], b = roads[i][1], dist = roads[i][2];
        
        Edge* edge1 = malloc(sizeof(Edge));
        edge1->to = b;
        edge1->dist = dist;
        edge1->next = graph[a].head;
        graph[a].head = edge1;
        
        Edge* edge2 = malloc(sizeof(Edge));
        edge2->to = a;
        edge2->dist = dist;
        edge2->next = graph[b].head;
        graph[b].head = edge2;
    }
    
    dfs(1, graph);
    return minScore;
}

int main() {
    int n;
    scanf("%d", &n);
    
    char line[10000];
    fgets(line, sizeof(line), stdin);
    fgets(line, sizeof(line), stdin);
    
    int roads[1000][3];
    int roadsSize = 0;
    
    char* ptr = line + 1; // Skip first '['
    while (*ptr && *ptr != ']') {
        if (*ptr == '[') {
            sscanf(ptr + 1, "%d,%d,%d", &roads[roadsSize][0], &roads[roadsSize][1], &roads[roadsSize][2]);
            roadsSize++;
        }
        ptr++;
    }
    
    printf("%d\n", solution(n, roads, roadsSize));
    return 0;
}

Time & Space Complexity

Time Complexity

⏱️

O(V + E)

Visit each vertex and edge once in the connected component

✓ Linear Growth

Space Complexity

O(V + E)

Adjacency list storage and recursion stack depth

✓ Linear Space

28.5K Views

Medium Frequency

~15 min Avg. Time

847 Likes

Ln 1, Col 1

Smart Actions

💡 Explanation

AI Ready

💡 Suggestion Tab to accept Esc to dismiss

// Output will appear here after running code

Code Editor Closed

Click the red button to reopen

Input & Output

Constraints

Visualization

Related Problems

Common Approaches

DFS Exploration — Algorithm Steps

Visualization

Code -

Time & Space Complexity

Select Compiler