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

Number of Ways to Arrive at Destination

Problem (yeniden ifade)

n kavşak (0 … n-1) ve çift yönlü yollar [u, v, time]. 0’dan n-1’e en kısa süreli kaç yol olduğunu 10^9+7 modunda döndür.

Sezgi

En kısa süreler için Dijkstra çalıştır, yanına ways[] koy. v’ye kesin daha iyi süre bulununca ways[u]’yu kopyala. Aynı süreli başka yol bulununca ways[u] ekle.

Yaklaşımlar

Dijkstra + yol sayıları

Doğrulanmadı

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

Fikir. dist[0] = 0, ways[0] = 1. nd = d + w gevşet: nd < dist[v] ise dist’i yaz, ways[v] = ways[u] ve it; nd == dist[v] ise ways[v] += ways[u] (mod). Eşit durumda tekrar itme — v ilk keşiften heap’te.

Yürüyüş. Sink’e süre 7 olan iki en kısa rota, ortak önek iki kez çatallanırsa resmi örnekteki 4 yol.

Trade-off. LC 743 Dijkstra’sı artı eşit-gevşetme dalı. 64-bit süre (n · 10^9). Çift saymamak için bayat pop’ları atla.

Çözüm

/**
 * Toy PQ: sort + shift. Interview/production: binary heap.
 */
export function countPaths(n: number, roads: number[][]): number {
  const MOD = 1_000_000_007;
  const adj: [number, number][][] = Array.from({ length: n }, () => []);
  for (const [u, v, t] of roads) {
    adj[u]!.push([v, t]);
    adj[v]!.push([u, t]);
  }
  const dist = new Array<number>(n).fill(Infinity);
  const ways = new Array<number>(n).fill(0);
  dist[0] = 0;
  ways[0] = 1;
  const pq: [number, number][] = [[0, 0]];
  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]!) {
      const nd = d + w;
      if (nd < dist[v]!) {
        dist[v] = nd;
        ways[v] = ways[u]!;
        pq.push([nd, v]);
      } else if (nd === dist[v]) {
        ways[v] = (ways[v]! + ways[u]!) % MOD;
      }
    }
  }
  return ways[n - 1]!;
}

/**
 * Toy PQ: sort + shift. Interview/production: binary heap.
 */
export function countPaths(n: number, roads: number[][]): number {
  const MOD = 1_000_000_007;
  const adj: [number, number][][] = Array.from({ length: n }, () => []);
  for (const [u, v, t] of roads) {
    adj[u]!.push([v, t]);
    adj[v]!.push([u, t]);
  }
  const dist = new Array<number>(n).fill(Infinity);
  const ways = new Array<number>(n).fill(0);
  dist[0] = 0;
  ways[0] = 1;
  const pq: [number, number][] = [[0, 0]];
  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]!) {
      const nd = d + w;
      if (nd < dist[v]!) {
        dist[v] = nd;
        ways[v] = ways[u]!;
        pq.push([nd, v]);
      } else if (nd === dist[v]) {
        ways[v] = (ways[v]! + ways[u]!) % MOD;
      }
    }
  }
  return ways[n - 1]!;
}

Şablon bağlantısı

Dijkstra, kesin iyileştirmede kopyalanan / berabere eklenen ekstra ways[] ile. Heap hâlâ yalnızca mesafeye göre.

Yansıma

Dijkstra en kısa süreyi tutar. Daha kısa yol sayacı sıfırlar, eşit yol ekler. Mod 10**9+7.
Kaynak süre 0, yol 1. Daha uzun yol sayılmaz. Sıfır ağırlık eşit yolu artırır.
Cevabı döngü bitince oku. Hedefi ilk pop ettiğinde sonraki eşit yol henüz eklenmemiş olabilir.