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

Hardshortest-path-weighted minimum-spanning-tree

Minimum Cost to Reach City With Discounts

Problem (yeniden ifade)

n şehir 0…n-1 ve çift yönlü otoyollar [c1, c2, toll]. En fazla discounts yarı fiyat kuponu kullanabilirsin (geçişin tabanı, her biri bir otoyol). 0’dan n-1’e min maliyeti döndür; ulaşılamazsa -1.

Sezgi

Kupon farklı algoritma değil, düğümün ekstra boyutudur. Durum (şehir, kullanılanKupon) üzerinde Dijkstra. Her durumdan sonraki otoyolu tam fiyata (aynı kupon sayısı) veya ⌊toll/2⌋ (kupon kaldıysa bir fazla) al. n-1 şehrinin ilk pop’u optimal.

Yaklaşımlar

İndirim durumlu Dijkstra

Doğrulanmadı

Zaman O((n+E)·d log (n d))Alan O(n d)

Fikir. dist[u][used]. Heap (cost, u, used). Ödenmemiş kenarı used’a, yarılanmış kenarı kupon varsa used+1’e gevşet. Bayat pop’ları atla. Sink hiç pop edilmezse -1.

Yürüyüş. 0-1-4, geçiş 4 ve 11, bir kupon: 4 öde sonra ⌊11/2⌋ = 5 → 9, kuponu daha küçük kenara saklamaktan ucuz.

Trade-off. LC 787 (duraklar) ile aynı ekstra-durum hamlesi. Yarılamayı tabana yuvarla, yukarı değil. discounts = 0 sıradan Dijkstra.

Çözüm

/**
 * Toy PQ: sort + shift. Interview/production: binary heap.
 * State is (cost, node, discountsUsed).
 */
export function minimumCost(n: number, highways: number[][], discounts: number): number {
  const adj: [number, number][][] = Array.from({ length: n }, () => []);
  for (const [a, b, c] of highways) {
    adj[a]!.push([b, c]);
    adj[b]!.push([a, c]);
  }
  const dist = Array.from({ length: n }, () => new Array<number>(discounts + 1).fill(Infinity));
  dist[0]![0] = 0;
  const pq: [number, number, number][] = [[0, 0, 0]];
  while (pq.length) {
    pq.sort((a, b) => a[0]! - b[0]!);
    const [d, u, used] = pq.shift()!;
    if (d > dist[u]![used]!) continue;
    if (u === n - 1) return d;
    for (const [v, w] of adj[u]!) {
      const nd = d + w;
      if (nd < dist[v]![used]!) {
        dist[v]![used] = nd;
        pq.push([nd, v, used]);
      }
      if (used < discounts) {
        const nd2 = d + Math.floor(w / 2);
        if (nd2 < dist[v]![used + 1]!) {
          dist[v]![used + 1] = nd2;
          pq.push([nd2, v, used + 1]);
        }
      }
    }
  }
  return -1;
}

/**
 * Toy PQ: sort + shift. Interview/production: binary heap.
 * State is (cost, node, discountsUsed).
 */
export function minimumCost(n: number, highways: number[][], discounts: number): number {
  const adj: [number, number][][] = Array.from({ length: n }, () => []);
  for (const [a, b, c] of highways) {
    adj[a]!.push([b, c]);
    adj[b]!.push([a, c]);
  }
  const dist = Array.from({ length: n }, () => new Array<number>(discounts + 1).fill(Infinity));
  dist[0]![0] = 0;
  const pq: [number, number, number][] = [[0, 0, 0]];
  while (pq.length) {
    pq.sort((a, b) => a[0]! - b[0]!);
    const [d, u, used] = pq.shift()!;
    if (d > dist[u]![used]!) continue;
    if (u === n - 1) return d;
    for (const [v, w] of adj[u]!) {
      const nd = d + w;
      if (nd < dist[v]![used]!) {
        dist[v]![used] = nd;
        pq.push([nd, v, used]);
      }
      if (used < discounts) {
        const nd2 = d + Math.floor(w / 2);
        if (nd2 < dist[v]![used + 1]!) {
          dist[v]![used + 1] = nd2;
          pq.push([nd2, v, used + 1]);
        }
      }
    }
  }
  return -1;
}

Şablon bağlantısı

Dijkstra + ekstra durum. Kuponlar cheapest-flights’taki k rolünü oynar. Katalog 2093’ü MST’ye de koyar; yazı buraya aittir çünkü algoritma en kısa yol, spanning tree değil.

Yansıma

Durum şehir artı kalan indirim. İndirimli kenar yarı fiyat, bir hak yer. Heap bu durumda.
Aynı şehre daha çok hakla varmak daha ucuz olabilir. Durumu tek şehir sanırsan o yolu kaçırırsın.
İndirim 0 düz Dijkstra. Hedefe ilk çıkış en ucuz. Ulaşılamazsa −1.