Сложность: medium
Есть n городов, соединенных некоторым количеством рейсов. Вам дан массив flights, где flights[i] = [fromi, toi, pricei] указывает на то, что существует рейс из города fromi в город toi с ценой pricei.
Также даны три целых числа src, dst и k. Верните самую дешевую цену от src до dst с не более чем k остановками. Если такого маршрута нет, верните -1.
Пример:
Input: n = 4, flights = [[0,1,100],[1,2,100],[2,0,100],[1,3,600],[2,3,200]], src = 0, dst = 3, k = 1
Output: 700
Explanation:
The graph is shown above.
The optimal path with at most 1 stop from city 0 to 3 is marked in red and has cost 100 + 600 = 700.
Note that the path through cities [0,1,2,3] is cheaper but is invalid because it uses 2 stops.
👨💻 Алгоритм:
1⃣Создайте список смежности, где adj[X] содержит всех соседей узла X и соответствующую цену, которую нужно заплатить, чтобы перейти к соседу. Инициализируйте массив dist, хранящий минимальную цену для достижения узла из узла src. Инициализируйте его большими значениями. Инициализируйте очередь, хранящую пары {node, distance}. Изначально очередь должна содержать только {src, 0}. Создайте переменную stops и установите ее значение равным 0.
2⃣Выполняйте поиск в ширину (BFS), пока очередь не станет пустой или пока stops > k. Итерируйте по всем узлам на определенном уровне. Это будет сделано путем запуска вложенного цикла и посещения всех узлов, которые в данный момент находятся в очереди. В каждой паре {node, distance} итерируйте по всем соседям узла. Для каждого соседа проверьте, меньше ли dist[neighbor] чем distance + цена ребра. Если это так, обновите dist[neighbor] и добавьте {neighbor, dist[neighbor]} в очередь.
3⃣После итерации по всем узлам на текущем уровне увеличьте stops на один. Мы посетили все узлы на определенном уровне и готовы посетить следующий уровень узлов. Когда мы достигнем условия, при котором либо очередь станет пустой, либо stops == k, у нас будет наш ответ в dist[dst]. Если dist[dst] не изменилось с начального большого значения, значит, мы никогда не достигли его, и следует вернуть -1.
😎 Решение:
import java.util.*;
class Solution {
public int findCheapestPrice(int n, int[][] flights, int src, int dst, int k) {
List<List<int[]>> adj = new ArrayList<>();
for (int i = 0; i < n; i++) {
adj.add(new ArrayList<>());
}
for (int[] flight : flights) {
adj.get(flight[0]).add(new int[]{flight[1], flight[2]});
}
int[] dist = new int[n];
Arrays.fill(dist, Integer.MAX_VALUE);
Queue<int[]> q = new LinkedList<>();
q.offer(new int[]{src, 0});
int stops = 0;
while (stops <= k && !q.isEmpty()) {
int sz = q.size();
for (int i = 0; i < sz; i++) {
int[] current = q.poll();
int node = current[0];
int distance = current[1];
for (int[] neighbor : adj.get(node)) {
int nextNode = neighbor[0];
int price = neighbor[1];
if (price + distance >= dist[nextNode]) continue;
dist[nextNode] = price + distance;
q.offer(new int[]{nextNode, dist[nextNode]});
}
}
stops++;
}
return dist[dst] == Integer.MAX_VALUE ? -1 : dist[dst];
}
}
Ставь 👍 и забирай 📚 Базу знаний