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

Network Delay Time

Problem (yeniden ifade)

n düğümlü (1-tabanlı) yönlü ağ ve ağırlıklı kenarlar times[i] = [u, v, w] (u’dan v’ye sinyal w sürer). Sinyal k’de başlar. Her düğümün alması için gereken süreyi döndür; bir düğüm ulaşılamazsa -1.

Sezgi

Son düğümün duyması, k’den en uzun en-kısa-yoldur. Ağırlıklar negatif değil, Dijkstra k’den. Cevap max(dist[1..n]), herhangi dist hâlâ sonsuzsa -1.

Yaklaşımlar

k'den Dijkstra

Doğrulanmadı

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

Fikir. (v, w) komşuluk listesi. dist[k] = 0, (d, u) min-heap. En yakın düğümü çek; bayat pop’ları atla (d > dist[u]); dist[v] = d + w gevşet ve it. Sonra sonlu mesafelerin max’ı.

Yürüyüş. n=4, k=2, kenarlar 2→1 (1), 2→3 (1), 3→4 (1). Mesafeler 1,0,1,2. Max 2.

Trade-off. Şablon. Ulaşılamayanlar ∞ kalır → -1. BFS yanlış olur: ucuz iki kenar, pahalı tek kenarı yenebilir.

Çözüm

/**
 * Toy PQ: sort + shift. Interview/production: binary heap, O((V+E) log V).
 */
export function networkDelayTime(times: number[][], n: number, k: number): number {
  const adj: [number, number][][] = Array.from({ length: n + 1 }, () => []);
  for (const [u, v, w] of times) adj[u]!.push([v, w]);
  const dist = new Array<number>(n + 1).fill(Infinity);
  dist[k] = 0;
  const pq: [number, number][] = [[0, k]];
  while (pq.length) {
    pq.sort((a, b) => a[0]! - b[0]!);
    const [d, u] = pq.shift()!;
    if (d > dist[u]!) continue;
    for (const [v, w] of adj[u]!) {
      if (d + w < dist[v]!) {
        dist[v] = d + w;
        pq.push([dist[v]!, v]);
      }
    }
  }
  let ans = 0;
  for (let i = 1; i <= n; i++) {
    if (dist[i] === Infinity) return -1;
    ans = Math.max(ans, dist[i]!);
  }
  return ans;
}

/**
 * Toy PQ: sort + shift. Interview/production: binary heap, O((V+E) log V).
 */
export function networkDelayTime(times: number[][], n: number, k: number): number {
  const adj: [number, number][][] = Array.from({ length: n + 1 }, () => []);
  for (const [u, v, w] of times) adj[u]!.push([v, w]);
  const dist = new Array<number>(n + 1).fill(Infinity);
  dist[k] = 0;
  const pq: [number, number][] = [[0, k]];
  while (pq.length) {
    pq.sort((a, b) => a[0]! - b[0]!);
    const [d, u] = pq.shift()!;
    if (d > dist[u]!) continue;
    for (const [v, w] of adj[u]!) {
      if (d + w < dist[v]!) {
        dist[v] = d + w;
        pq.push([dist[v]!, v]);
      }
    }
  }
  let ans = 0;
  for (let i = 1; i <= n; i++) {
    if (dist[i] === Infinity) return -1;
    ans = Math.max(ans, dist[i]!);
  }
  return ans;
}

Şablon bağlantısı

Düz Dijkstra: mesafeye göre min-heap, pop’ta gevşet, bayat girdileri atla. LC 1976 aynı döngü artı yol sayıları.

Yansıma

Kaynak k. Min-heap (süre, düğüm). İlk çıkış en kısa süre. Cevap ulaşılabilen en geç düğüm.
Biri k’dan kopuksa −1. Negatif ağırlık yok. Daha büyük süreyle aynı düğümü tekrar işleme.
n = 1 cevap 0. Kenar yok ve n > 1 ise cevap −1.