787. Cheapest Flights Within K Stops

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];
    }
}

#include <bits/stdc++.h>
using namespace std;

// Auto-generated C++ draft from the C# solution. Review containers, LINQ and helper types before submit.
class Solution {
public:
    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]].push_back((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.size() > 0) {
            int sz = q.size();
            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];
    }
}

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];
    }
}

class Solution {
    findCheapestPrice(n, flights, src, dst, k) {
        const adj = Array.from({ length: n }, () => []);
        for (const [from, to, price] of flights) {
            adj[from].push([to, price]);
        }
        const dist = Array(n).fill(Infinity);
        const q = [[src, 0]];
        let stops = 0;

        while (stops <= k && q.length) {
            const size = q.length;
            for (let i = 0; i < size; i++) {
                const [node, distance] = q.shift();
                for (const [neighbor, price] of adj[node]) {
                    if (price + distance >= dist[neighbor]) continue;
                    dist[neighbor] = price + distance;
                    q.push([neighbor, dist[neighbor]]);
                }
            }
            stops++;
        }
        return dist[dst] === Infinity ? -1 : dist[dst];
    }
}

Explanation

Algorithm

Создайте список смежности, где adj[X] содержит всех соседей узла X и соответствующую цену, которую нужно заплатить, чтобы перейти к соседу. Инициализируйте массив dist, хранящий минимальную цену для достижения узла из узла src. Инициализируйте его большими значениями. Инициализируйте очередь, хранящую пары {node, distance}. Изначально очередь должна содержать только {src, 0}. Создайте переменную stops и установите ее значение равным 0.

Выполняйте поиск в ширину (BFS), пока очередь не станет пустой или пока stops > k. Итерируйте по всем узлам на определенном уровне. Это будет сделано путем запуска вложенного цикла и посещения всех узлов, которые в данный момент находятся в очереди. В каждой паре {node, distance} итерируйте по всем соседям узла. Для каждого соседа проверьте, меньше ли dist[neighbor] чем distance + цена ребра. Если это так, обновите dist[neighbor] и добавьте {neighbor, dist[neighbor]} в очередь.

После итерации по всем узлам на текущем уровне увеличьте stops на один. Мы посетили все узлы на определенном уровне и готовы посетить следующий уровень узлов. Когда мы достигнем условия, при котором либо очередь станет пустой, либо stops == k, у нас будет наш ответ в dist[dst]. Если dist[dst] не изменилось с начального большого значения, значит, мы никогда не достигли его, и следует вернуть -1.

😎