Сложность: 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.
😎 Решение:
using System;
using System.Collections.Generic;
public class Solution {
public int FindCheapestPrice(int n, int[][] flights, int src, int dst, int k) {
var adj = new List<(int, int)>[n];
for (int i = 0; i < n; i++) adj[i] = new List<(int, int)>();
foreach (var flight in flights) {
adj[flight[0]].Add((flight[1], flight[2]));
}
var dist = new int[n];
Array.Fill(dist, int.MaxValue);
var q = new Queue<(int node, int distance)>();
q.Enqueue((src, 0));
int stops = 0;
while (stops <= k && q.Count > 0) {
int sz = q.Count;
for (int i = 0; i < sz; i++) {
var (node, distance) = q.Dequeue();
foreach (var (neighbour, price) in adj[node]) {
if (price + distance >= dist[neighbour]) continue;
dist[neighbour] = price + distance;
q.Enqueue((neighbour, dist[neighbour]));
}
}
stops++;
}
return dist[dst] == int.MaxValue ? -1 : dist[dst];
}
}
Ставь 👍 и забирай 📚 Базу знаний