Skip to content

Binary Resource

You have one coupon. One. It halves the cost of any single flight. You can use it on the cheapest flight and waste it, or save it for the most expensive one and change your entire route. This single binary decision --- used or not used --- doubles your graph. And that doubling is the simplest, cleanest entry point into state-expanded Dijkstra.

The Problem: CSES Flight Discount

2-layer expansion: discount unused vs discount used

Toll-free edge model: 2-layer graph where toll moves to upper layer

\(N\) cities, \(M\) directed flights with costs. You have one coupon that halves the cost of any single flight. Find the cheapest path from city 1 to city \(N\).

Constraints: \(N \le 10^5\), \(M \le 2 \times 10^5\).

Without the coupon, this is textbook Dijkstra. The coupon adds a binary resource: you either still have it (state 0) or you've spent it (state 1).

The State

\[\text{dist}[\text{city}][\text{used}]\]
  • dist[city][0] = cheapest cost to reach city without having used the coupon.
  • dist[city][1] = cheapest cost to reach city having already used the coupon somewhere along the path.

Two layers. That's it. The resource is a single bit.

The Transitions

From state (u, 0) --- coupon still available:

  1. Don't use coupon: go to (v, 0) with cost \(w\). Coupon stays in your pocket.
  2. Use coupon here: go to (v, 1) with cost \(\lfloor w/2 \rfloor\). Coupon is spent.

From state (u, 1) --- coupon already used:

  1. Only option: go to (v, 1) with cost \(w\). No coupon available.

Key insight. Transitions from layer 0 can go to layer 0 or layer 1. Transitions from layer 1 stay in layer 1. Information never flows backward --- once you use the coupon, you can't un-use it.

The Expanded Graph

Visualize two copies of the original graph stacked on top of each other:

Layer 0 (coupon available):    1 --5--> 2 --3--> 3
                                \               |
                        use      \             |
                       coupon     \           |
                                   v         v
Layer 1 (coupon spent):            2 --3--> 3
                               1 --5--> 2 --3--> 3

Edges within layer 0: full cost, coupon stays. Edges from layer 0 to layer 1: half cost, coupon consumed. Edges within layer 1: full cost, no coupon.

Total vertices: \(2N\). Total edges: at most \(3M\) (each original edge spawns up to 3 expanded edges). Dijkstra runs in \(O(M \log N)\) --- barely slower than vanilla.

Full Trace

Graph: 4 cities. Flights: 1->2 (10), 1->3 (6), 2->4 (8), 3->4 (12).

Step Pop (cost, city, used) Updates
1 (0, 1, 0) dist[2][0]=10, dist[3][0]=6, dist[2][1]=5, dist[3][1]=3
2 (3, 3, 1) dist[4][1]=15
3 (5, 2, 1) dist[4][1]=13 (improve!)
4 (6, 3, 0) dist[4][0]=18, dist[4][1]=12 (improve!)
5 (10, 2, 0) dist[4][0]=18 (no improve), dist[4][1]=14 (no improve)
6 (12, 4, 1) destination reached

Answer: \(\min(\text{dist}[4][0], \text{dist}[4][1]) = \min(18, 12) = 12\).

Best path: \(1 \to 3\) (cost 6, no coupon) \(\to 4\) (cost 12, use coupon \(\to\) cost 6). Total: \(6 + 6 = 12\).

The Code

#include <bits/stdc++.h>
using namespace std;

int main() {
    int n, m;
    cin >> n >> m;
    vector<vector<pair<int,long long>>> adj(n + 1);
    for (int i = 0; i < m; i++) {
        int u, v;
        long long w;
        cin >> u >> v >> w;
        adj[u].push_back({v, w});
    }

    vector<vector<long long>> dist(n + 1, vector<long long>(2, LLONG_MAX));
    priority_queue<tuple<long long,int,int>,
                   vector<tuple<long long,int,int>>,
                   greater<>> pq;
    dist[1][0] = 0;
    pq.push({0, 1, 0});

    while (!pq.empty()) {
        auto [d, u, used] = pq.top(); pq.pop();
        if (d > dist[u][used]) continue;
        for (auto [v, w] : adj[u]) {
            if (d + w < dist[v][used]) {
                dist[v][used] = d + w;
                pq.push({d + w, v, used});
            }
            if (used == 0 && d + w / 2 < dist[v][1]) {
                dist[v][1] = d + w / 2;
                pq.push({d + w / 2, v, 1});
            }
        }
    }

    cout << min(dist[n][0], dist[n][1]) << "\n";
    return 0;
}

The Two-Dijkstra Alternative

There's a clever way to solve Flight Discount without state expansion at all.

Run Dijkstra forward from node 1: compute fwd[u] = shortest distance from 1 to every node \(u\).

Run Dijkstra backward from node \(N\) (on reversed edges): compute bwd[v] = shortest distance from every node \(v\) to \(N\).

For each edge \((u, v, w)\), the best path that uses the coupon on THIS specific edge costs:

\[\text{fwd}[u] + \lfloor w/2 \rfloor + \text{bwd}[v]\]

The answer is the minimum of this over all edges, plus fwd[N] (the no-coupon option).

long long ans = fwd[n];
for (int u = 1; u <= n; u++) {
    for (auto [v, w] : adj[u]) {
        if (fwd[u] != LLONG_MAX && bwd[v] != LLONG_MAX) {
            ans = min(ans, fwd[u] + w / 2 + bwd[v]);
        }
    }
}

This runs two standard Dijkstras plus one pass over all edges. Same complexity, no state expansion. But it only works because the resource is binary --- you use the coupon on exactly one edge.

Gotcha. The two-Dijkstra trick doesn't generalize to K coupons. For K > 1, you need state expansion.

Same Pattern: AtCoder abc325_e (Our Clients)

Two transport modes: car and train. Car is available first; at some point you switch to train and never switch back. The switch is your binary resource.

State: (city, switched_to_train).

  • dist[city][0] = using car. Transitions: car edges only, or switch to train at this city.
  • dist[city][1] = using train. Transitions: train edges only.

The structure is identical to Flight Discount. Layer 0 can jump to layer 1. Layer 1 stays in layer 1. One binary decision that never reverses.

When You See It

The binary resource pattern appears whenever:

  • You have one special action (coupon, mode switch, toll bypass).
  • The action is irreversible --- once used, it's gone.
  • The action changes the cost structure of future edges.

Two layers. Two copies of the graph. One-way bridges between them.

Exercises

  1. Edge case. What if the coupon makes a flight free (cost 0) instead of half-price? Does the algorithm change?

  2. Reversed coupon. What if the coupon doubles the cost of one flight, and you're forced to use it exactly once? How does the transition logic change?

  3. Two-Dijkstra proof. Why does the two-Dijkstra approach work? Argue that the optimal path must use the coupon on exactly one edge, and that edge splits the path into a prefix (source to \(u\)) and a suffix (\(v\) to destination).

Problems

Problem Link Difficulty
CSES — Flight Discount cses.fi/problemset/task/1195 Medium
AtCoder abc325_e — Our Clients atcoder.jp/contests/abc325/tasks/abc325_e Medium
LC 2093 — Min Cost to Reach City With Discounts leetcode.com/problems/minimum-cost-to-reach-city-with-discounts Medium