LeetCode 2492: Minimum Score of a Path Between Two Cities
Problem Description
Explanation:
To find the minimum score of a path between cities 1 and n, we can use Dijkstra's algorithm. We will start from city 1 and explore all possible paths to other cities while keeping track of the minimum distance encountered so far. Once we reach city n, we will have the minimum score of a path between cities 1 and n.
- Create an adjacency list to represent the graph where each city is connected to its neighboring cities with corresponding distances.
- Initialize a priority queue (min heap) to store the cities to explore based on the minimum distance encountered so far.
- Initialize an array to store the minimum distances from city 1 to each city.
- Start with city 1, add it to the priority queue with distance 0.
- While the priority queue is not empty, pop the city with the minimum distance.
- For each neighboring city of the popped city, update the minimum distance if a shorter path is found and add the neighboring city to the priority queue.
- Continue this process until we reach city n.
- The minimum score of the path between cities 1 and n will be the minimum distance encountered at city n.
Time Complexity: O(ElogV), where E is the number of roads and V is the number of cities. Space Complexity: O(V + E), where V is the number of cities and E is the number of roads.
Solutions
import java.util.*;
class Solution {
public int minimumScore(int n, int[][] roads) {
Map<Integer, List<int[]>> graph = new HashMap<>();
for (int[] road : roads) {
graph.computeIfAbsent(road[0], k -> new ArrayList<>()).add(new int[]{road[1], road[2]});
graph.computeIfAbsent(road[1], k -> new ArrayList<>()).add(new int[]{road[0], road[2]});
}
PriorityQueue<int[]> pq = new PriorityQueue<>((a, b) -> a[1] - b[1]);
int[] dist = new int[n + 1];
Arrays.fill(dist, Integer.MAX_VALUE);
pq.offer(new int[]{1, 0});
dist[1] = 0;
while (!pq.isEmpty()) {
int[] curr = pq.poll();
int city = curr[0];
int distance = curr[1];
if (city == n) {
return distance;
}
if (distance > dist[city]) {
continue;
}
if (graph.containsKey(city)) {
for (int[] neighbor : graph.get(city)) {
int nextCity = neighbor[0];
int nextDist = Math.min(distance, neighbor[1]);
if (nextDist < dist[nextCity]) {
dist[nextCity] = nextDist;
pq.offer(new int[]{nextCity, nextDist});
}
}
}
}
return -1;
}
}Loading editor...