Demo önizleme: Bu çözümler otomatik test paketini geçiyor ama insan tarafından incelenmedi. Trade-off ve yazıları taslak olarak değerlendirin.

Mediumshortest-path-weighted

Cheapest Flights Within K Stops

Problem (yeniden ifade)

n şehir ve yönlü uçuşlar [from, to, price]. src’den dst’ye en fazla k durak (yani en fazla k+1 uçuş) ile en ucuz fiyatı döndür. İmkansızsa -1.

Sezgi

Daha ucuz yol bütçeden fazla durak kullanabilir, bu yüzden düz Dijkstra (ilk pop en ucuz, hop sayısı serbest) yanlıştır. Ya her kenarı k+1 kez gevşet (Bellman-Ford, tur başına bir hop) ya da Dijkstra durumuna durak koy.

Yaklaşımlar

Bellman-Ford k+1 tur

Doğrulanmadı

Zaman O(k·E)Alan O(n)

Fikir. dist[src] = 0. k+1 tur, dist’i nxt’e kopyala ve her uçuşu önceki tura göre gevşet ki her tur en fazla bir hop eklesin. Cevap dist[dst].

Yürüyüş. src=0, dst=2, k=1, uçuşlar 0→1 (100), 1→2 (100), 0→2 (500). 1 hop sonra: direkt 500. 2 hop sonra: 0-1-2 ile 200.

Trade-off. Basit, heap yok. Her tur dist’i kopyala, yoksa fazla hop sızar. k = 0 tek tur.

Çözüm

export function findCheapestPrice(
  n: number,
  flights: number[][],
  src: number,
  dst: number,
  k: number,
): number {
  let dist = new Array<number>(n).fill(Infinity);
  dist[src] = 0;
  for (let i = 0; i <= k; i++) {
    const nxt = dist.slice();
    for (const [u, v, w] of flights) {
      if (dist[u]! + w < nxt[v]!) nxt[v] = dist[u]! + w;
    }
    dist = nxt;
  }
  return dist[dst] === Infinity ? -1 : dist[dst]!;
}

export function findCheapestPrice(
  n: number,
  flights: number[][],
  src: number,
  dst: number,
  k: number,
): number {
  let dist = new Array<number>(n).fill(Infinity);
  dist[src] = 0;
  for (let i = 0; i <= k; i++) {
    const nxt = dist.slice();
    for (const [u, v, w] of flights) {
      if (dist[u]! + w < nxt[v]!) nxt[v] = dist[u]! + w;
    }
    dist = nxt;
  }
  return dist[dst] === Infinity ? -1 : dist[dst]!;
}

Durak durumlu Dijkstra

Doğrulanmadı

Zaman O(k·E log (k n))Alan O(k n)

Fikir. Heap (cost, node, edgesUsed). best[v][edges] o hop sayısıyla v’ye en ucuz. dst ilk pop edildiğinde maliyet optimal. k+1 kenarda genişlemeyi kes.

Yürüyüş. Aynı graf. 200, 500’den küçük olduğu için önce pop edilir.

Trade-off. Dijkstra diye düşünüyorsan bu. Düğümü ilk ziyarette kilitleme: daha az hop’lu pahalı rota sonra kazanabilir.

Çözüm

/**
 * Toy PQ: sort + shift. Interview/production: binary heap.
 * State is (cost, node, edgesUsed) so a cheaper-with-more-stops path
 * cannot hide a costlier-with-fewer-stops path that still reaches dst.
 */
export function findCheapestPrice(
  n: number,
  flights: number[][],
  src: number,
  dst: number,
  k: number,
): number {
  const adj: [number, number][][] = Array.from({ length: n }, () => []);
  for (const [u, v, w] of flights) adj[u]!.push([v, w]);
  const best = Array.from({ length: n }, () => new Array<number>(k + 2).fill(Infinity));
  best[src]![0] = 0;
  const pq: [number, number, number][] = [[0, src, 0]];
  while (pq.length) {
    pq.sort((a, b) => a[0]! - b[0]!);
    const [cost, u, edges] = pq.shift()!;
    if (u === dst) return cost;
    if (edges === k + 1) continue;
    for (const [v, w] of adj[u]!) {
      const nc = cost + w;
      if (nc < best[v]![edges + 1]!) {
        best[v]![edges + 1] = nc;
        pq.push([nc, v, edges + 1]);
      }
    }
  }
  return -1;
}

/**
 * Toy PQ: sort + shift. Interview/production: binary heap.
 * State is (cost, node, edgesUsed) so a cheaper-with-more-stops path
 * cannot hide a costlier-with-fewer-stops path that still reaches dst.
 */
export function findCheapestPrice(
  n: number,
  flights: number[][],
  src: number,
  dst: number,
  k: number,
): number {
  const adj: [number, number][][] = Array.from({ length: n }, () => []);
  for (const [u, v, w] of flights) adj[u]!.push([v, w]);
  const best = Array.from({ length: n }, () => new Array<number>(k + 2).fill(Infinity));
  best[src]![0] = 0;
  const pq: [number, number, number][] = [[0, src, 0]];
  while (pq.length) {
    pq.sort((a, b) => a[0]! - b[0]!);
    const [cost, u, edges] = pq.shift()!;
    if (u === dst) return cost;
    if (edges === k + 1) continue;
    for (const [v, w] of adj[u]!) {
      const nc = cost + w;
      if (nc < best[v]![edges + 1]!) {
        best[v]![edges + 1] = nc;
        pq.push([nc, v, edges + 1]);
      }
    }
  }
  return -1;
}

Şablon bağlantısı

Dijkstra + ekstra durum (duraklar), veya yol uzunluğuyla sınırlı Bellman-Ford. LC 2093 (indirimler) ile aynı “algoritmayı değil durumu genişlet” hamlesi.

Yansıma

En fazla k aktarma, k+1 kenar. Her tur bir önceki turun mesafesinden gevşer. Aynı turu kullanırsan fazla kenar sayarsın.
Duraklı Dijkstra da aynı cevabı verir. Ulaşılamazsa −1.
k = 0 yalnız doğrudan kenar. Pozitif fiyat. Tur sınırı negatif döngüyü keser.