source: https://leetcode.com/problems/minimum-score-of-a-path-between-two-cities/
Minimum Score of a Path Between Two Cities
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 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.
Example 1:
Input: n = 4, roads = [[1,2,9],[2,3,6],[2,4,5],[1,4,7]]
Output: 5
Explanation: The path from city 1 to 4 with the minimum score is: 1 -> 2 -> 4. The score of this path is min(9,5) = 5.
It can be shown that no other path has less score.
Example 2:
Input: n = 4, roads = [[1,2,2],[1,3,4],[3,4,7]]
Output: 2
Explanation: The path from city 1 to 4 with the minimum score is: 1 -> 2 -> 1 -> 3 -> 4. The score of this path is min(2,2,4,7) = 2.
Constraints:
- 2 <= n <= 105
- 1 <= roads.length <= 105
- roads[i].length == 3
- 1 <= ai, bi <= n
- ai != bi
- 1 <= distancei <= 104
- There are no repeated edges.
- There is at least one path between 1 and n.
|
1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 26 27 28 29 30 31 32 33 34 35 36 37 38 39 40 41 42 43 44 45 |
class Solution { public int minScore(int n, int[][] roads) { Map<Integer, List<Pair>> map = new HashMap<>(); for(int[] road: roads){ map.computeIfAbsent(road[0], k->new ArrayList<>()).add(new Pair(road[1], road[2])); map.computeIfAbsent(road[1], k->new ArrayList<>()).add(new Pair(road[0], road[2])); } return bfs(map); } private int bfs(Map<Integer, List<Pair>> map){ ArrayDeque<Pair> next = new ArrayDeque<>(); next.add(new Pair(1, Integer.MAX_VALUE)); HashSet<String> seen = new HashSet<>(); int min = Integer.MAX_VALUE; while(!next.isEmpty()){ int size = next.size(); for(int i=0;i<size;i++){ Pair p = next.poll(); min = Math.min(min, p.dist); for(Pair adj: map.get(p.val)){ //There are no repeated edges. //if we have not seen the edge add it to the set if(!seen.contains(p.val+":"+adj.val)){ seen.add(p.val+":"+adj.val); seen.add(adj.val+":"+p.val); next.add(adj); } } } } return min; } static class Pair{ int val; int dist; public Pair(int val, int dist){ this.val = val; this.dist = dist; } } } |
n: number of roads
Time Complexity
O(n): we need to visit all the edges in a connected component exactly once
Space Complexity
O(n): to store n roads in a map