Minimum Cost to Reach City With Discounts

Problem (restated)

n cities 0…n-1 and bidirectional highways [c1, c2, toll]. You may apply at most discounts half-price coupons (floor of the toll, one highway each). Return the min cost from 0 to n-1, or -1 if unreachable.

Intuition

A coupon is an extra dimension on the node, not a different algorithm. Dijkstra on state (city, couponsUsed). From each state, take the next highway at full price (same coupon count) or at ⌊toll/2⌋ (one more coupon, if any remain). First pop of city n-1 is optimal.

Approaches

/**
 * 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;
}

Template connection

Dijkstra + extra state. Coupons play the role k played in cheapest-flights. Catalog also lists 2093 under MST; the write-up belongs here because the algorithm is shortest path, not spanning tree.

Reflection

• The state is (city, discounts still left). A discounted edge costs half and spends one discount. The heap orders those states.
• Reaching the same city with more discounts left can be cheaper. Collapsing the state to the city alone drops that path.
• discounts = 0 is ordinary Dijkstra. The first pop of the destination is the cheapest. Unreachable is −1.