Second Minimum Time to Reach Destination

Problem (yeniden ifade)

Düğümler 1…n üzerinde yönsüz, ağırlıksız graf. Her kenar time dakika. Her düğümde trafik ışığı: change dakika yeşil, sonra change dakika kırmızı, t=0’da yeşil başlar. Yalnızca yeşilken ayrılabilirsin (kırmızıda bekle). 1’den n’ye ikinci-minimum varış süresini döndür.

Sezgi

n’de iki farklı varış süresi gerekir, her düğüm birinci ve (kesin daha büyük) ikinci zaman tutar. Varışa göre Dijkstra/BFS. Ayrılmadan önce ⌊t / change⌋ tekse bir sonraki yeşili bekle: t += change - t % change. Sonra her komşu t + time’da varır.

Yaklaşımlar

/**
 * Toy PQ: sort + shift. Interview/production: binary heap.
 * Each node keeps first and second arrival; leave only on green.
 */
export function secondMinimum(
  n: number,
  edges: number[][],
  time: number,
  change: number,
): number {
  const adj: number[][] = Array.from({ length: n + 1 }, () => []);
  for (const [a, b] of edges) {
    adj[a]!.push(b);
    adj[b]!.push(a);
  }
  const dist1 = new Array<number>(n + 1).fill(Infinity);
  const dist2 = new Array<number>(n + 1).fill(Infinity);
  dist1[1] = 0;
  const pq: [number, number][] = [[0, 1]];
  while (pq.length) {
    pq.sort((a, b) => a[0]! - b[0]!);
    let [t, u] = pq.shift()!;
    if (u === n && t > dist1[n]!) return t;
    if (Math.floor(t / change) % 2 === 1) t += change - (t % change);
    for (const v of adj[u]!) {
      const nt = t + time;
      if (nt < dist1[v]!) {
        dist2[v] = dist1[v]!;
        dist1[v] = nt;
        pq.push([nt, v]);
      } else if (nt > dist1[v]! && nt < dist2[v]!) {
        dist2[v] = nt;
        pq.push([nt, v]);
      }
    }
  }
  return dist2[n]!;
}

/**
 * Toy PQ: sort + shift. Interview/production: binary heap.
 * Each node keeps first and second arrival; leave only on green.
 */
export function secondMinimum(
  n: number,
  edges: number[][],
  time: number,
  change: number,
): number {
  const adj: number[][] = Array.from({ length: n + 1 }, () => []);
  for (const [a, b] of edges) {
    adj[a]!.push(b);
    adj[b]!.push(a);
  }
  const dist1 = new Array<number>(n + 1).fill(Infinity);
  const dist2 = new Array<number>(n + 1).fill(Infinity);
  dist1[1] = 0;
  const pq: [number, number][] = [[0, 1]];
  while (pq.length) {
    pq.sort((a, b) => a[0]! - b[0]!);
    let [t, u] = pq.shift()!;
    if (u === n && t > dist1[n]!) return t;
    if (Math.floor(t / change) % 2 === 1) t += change - (t % change);
    for (const v of adj[u]!) {
      const nt = t + time;
      if (nt < dist1[v]!) {
        dist2[v] = dist1[v]!;
        dist1[v] = nt;
        pq.push([nt, v]);
      } else if (nt > dist1[v]! && nt < dist2[v]!) {
        dist2[v] = nt;
        pq.push([nt, v]);
      }
    }
  }
  return dist2[n]!;
}

Şablon bağlantısı

Dijkstra + ekstra durum; burada (düğüm, k) yerine düğüm başına ikinci mesafe. LC 787 ile aynı “ilk pop’ta durma” fikri.

Yansıma

• Her düğümde ilk ve ikinci varış. Aday birinciden küçükse birinci kayar. Birinci ile ikinci arasındaysa ikinci olur.
• Eşit süre ikinci sayılmaz. Hedefi, birinciden sıkı büyük bir süreyle ilk pop ettiğinde o cevap.
• Işık: t / change tabanı tekse kırmızıdasın; ayrılmadan sonraki yeşile kadar bekle. Saklanan süre varıştır. n = 2 doğrudan kenar.