Skip to content

Multi-Criteria

Shortest path gives you one number: the distance. But real problems ask for more. "Find the shortest path, and among those, maximize the souvenirs." Or "count all shortest paths, and also report the one with fewest edges." When you optimize two things at once, your distance table stops holding a single value --- it holds a tuple.

Problem 1: ABC286-E Souvenir

Pareto frontier: non-dominated paths in multi-objective optimization

\(N\) cities, directed graph. Each city \(i\) has a souvenir value \(v[i]\). For \(Q\) queries \((s, t)\): find the path minimizing hops, and among all minimum-hop paths, maximize total souvenir value. If no path exists, output "Impossible."

The Two-Criteria State

Define \(\text{dp}[i][j]\) as a pair: (minimum hops, maximum souvenir value). Compare lexicographically:

  • Fewer hops always wins.
  • Among paths with equal hops, more souvenir value wins.

This is a modified Floyd-Warshall. The relaxation step becomes:

// Going i -> k -> j
State through_k = {
    dp[i][k].hops + dp[k][j].hops,
    dp[i][k].value + dp[k][j].value - val[k]  // don't double-count k
};
if (through_k < dp[i][j])
    dp[i][j] = through_k;

The comparison operator encodes the lexicographic priority:

bool operator<(const State& o) const {
    if (hops != o.hops) return hops < o.hops;   // fewer hops first
    return value > o.value;                       // then more value
}

Key insight. Lexicographic comparison on tuples is the clean way to handle multi-criteria optimization. The first criterion dominates. The second breaks ties. You never mix them --- no weighted sums, no heuristics.

Full Solution

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

int main() {
    int n, m;
    cin >> n >> m;
    vector<long long> val(n);
    for (int i = 0; i < n; i++) cin >> val[i];

    const int INF = 1e9;
    // dp[i][j] = {min_hops, max_value}
    vector<vector<pair<int,long long>>> dp(n,
        vector<pair<int,long long>>(n, {INF, 0}));

    for (int i = 0; i < n; i++)
        dp[i][i] = {0, val[i]};

    for (int i = 0; i < m; i++) {
        int u, v;
        cin >> u >> v;
        u--; v--;
        pair<int,long long> cand = {1, val[u] + val[v]};
        if (cand.first < dp[u][v].first ||
            (cand.first == dp[u][v].first && cand.second > dp[u][v].second))
            dp[u][v] = cand;
    }

    // Floyd-Warshall with lexicographic comparison
    for (int k = 0; k < n; k++)
        for (int i = 0; i < n; i++)
            for (int j = 0; j < n; j++) {
                if (dp[i][k].first == INF || dp[k][j].first == INF) continue;
                int h = dp[i][k].first + dp[k][j].first;
                long long v = dp[i][k].second + dp[k][j].second - val[k];
                if (h < dp[i][j].first ||
                    (h == dp[i][j].first && v > dp[i][j].second))
                    dp[i][j] = {h, v};
            }

    int q;
    cin >> q;
    while (q--) {
        int s, t;
        cin >> s >> t;
        s--; t--;
        if (dp[s][t].first == INF)
            cout << "Impossible\n";
        else
            cout << dp[s][t].first << " " << dp[s][t].second << "\n";
    }
}

Trace: 4-City Souvenir

Cities: 0, 1, 2, 3. Values: \([10, 20, 30, 40]\).

Edges: \(0 \to 1\), \(1 \to 2\), \(0 \to 2\), \(2 \to 3\).

Initial dp (after direct edges):

0 1 2 3
0 (0, 10) (1, 30) (1, 40) (\(\infty\), 0)
1 (\(\infty\), 0) (0, 20) (1, 50) (\(\infty\), 0)
2 (\(\infty\), 0) (\(\infty\), 0) (0, 30) (1, 70)
3 (\(\infty\), 0) (\(\infty\), 0) (\(\infty\), 0) (0, 40)

Floyd, \(k = 0\): no improvements (0 doesn't help reach new places).

Floyd, \(k = 1\): check \(i = 0, j = 2\). Through 1: hops = \(1 + 1 = 2\), value = \(30 + 50 - 20 = 60\). Current: (1, 40). 2 hops > 1 hop, no update.

Floyd, \(k = 2\): check \(i = 0, j = 3\). Through 2: hops = \(1 + 1 = 2\), value = \(40 + 70 - 30 = 80\). Current: (\(\infty\), 0). Update to (2, 80).

Check \(i = 1, j = 3\). Through 2: hops = \(1 + 1 = 2\), value = \(50 + 70 - 30 = 90\). Update to (2, 90).

Floyd, \(k = 3\): no improvements.

Final dp:

0 1 2 3
0 (0, 10) (1, 30) (1, 40) (2, 80)
1 (\(\infty\), 0) (0, 20) (1, 50) (2, 90)
2 (\(\infty\), 0) (\(\infty\), 0) (0, 30) (1, 70)
3 (\(\infty\), 0) (\(\infty\), 0) (\(\infty\), 0) (0, 40)

Query \((0, 3)\): 2 hops, value 80. Path: \(0 \to 2 \to 3\), collecting \(10 + 30 + 40 = 80\).

Gotcha. When combining paths through \(k\), subtract \(\text{val}[k]\) to avoid double-counting. City \(k\) appears at the end of the \(i \to k\) path and at the start of the \(k \to j\) path. Its souvenir is collected once, not twice.

Problem 2: CSES Investigation

\(N\) cities, \(M\) flights with costs. Find from city 1 to city \(N\):

  1. The minimum cost.
  2. The number of minimum-cost routes (mod \(10^9 + 7\)).
  3. The minimum number of flights on any minimum-cost route.
  4. The maximum number of flights on any minimum-cost route.

Four outputs, one Dijkstra. Track a 4-tuple per node.

vector<long long> dist(n, LLONG_MAX);
vector<long long> cnt(n, 0);
vector<int> mn(n, INT_MAX), mx(n, 0);

dist[0] = 0; cnt[0] = 1; mn[0] = 0; mx[0] = 0;

// During Dijkstra relaxation:
if (nd < dist[v]) {
    dist[v] = nd;
    cnt[v] = cnt[u];
    mn[v] = mn[u] + 1;
    mx[v] = mx[u] + 1;
    pq.push({nd, v});
} else if (nd == dist[v]) {
    cnt[v] = (cnt[v] + cnt[u]) % MOD;
    mn[v] = min(mn[v], mn[u] + 1);
    mx[v] = max(mx[v], mx[u] + 1);
}

Key insight. The nd < dist[v] case resets all criteria --- a shorter path invalidates everything we knew. The nd == dist[v] case merges --- we found another shortest path, so add its count and update the edge extremes.

Trace: CSES Investigation

Nodes: 4. Edges: \(0 \to 1\) (2), \(0 \to 2\) (4), \(1 \to 2\) (1), \(1 \to 3\) (5), \(2 \to 3\) (3).

Step Pop (d, u) Relax dist cnt mn mx
1 (0, 0) \(\to\)1: d=2, \(\to\)2: d=4 [0, 2, 4, \(\infty\)] [1,1,1,0] [0,1,1,\(\infty\)] [0,1,1,0]
2 (2, 1) \(\to\)2: d=3 < 4, \(\to\)3: d=7 [0, 2, 3, 7] [1,1,1,1] [0,1,2,2] [0,1,2,2]
3 (3, 2) \(\to\)3: d=6 < 7 [0, 2, 3, 6] [1,1,1,1] [0,1,2,3] [0,1,2,3]
4 (4, 2) stale (dist[2]=3) skip
5 (6, 3) destination done

Wait --- we also pushed (4, 2) from step 1. When we pop it, dist[2] = 3 < 4, so we skip. But we should check: does the path \(0 \to 2\) (cost 4) produce nd == dist[2]? No, 4 \(\neq\) 3.

But what about \(0 \to 2\) directly (cost 4), then \(2 \to 3\) (cost 3)? That gives cost 7, same as \(0 \to 1 \to 3\) (cost 7). Neither is the shortest to node 3 (which is 6). So only one shortest path to node 3.

Answer: dist = 6, count = 1, min flights = 3, max flights = 3.

Problem 3: CSES Flight Routes (K Shortest Paths)

Find the \(K\) shortest path distances from city 1 to city \(N\). This is a classic application of the "K-best per node" technique.

Instead of storing one distance per node, store up to \(K\) distances. Process each arrival at a node, but only if we haven't already recorded \(K\) arrivals there.

vector<vector<long long>> best(n);
priority_queue<pair<long long,int>,
               vector<pair<long long,int>>,
               greater<>> pq;
pq.push({0, 0});

while (!pq.empty()) {
    auto [d, u] = pq.top(); pq.pop();
    best[u].push_back(d);
    if (u == n - 1 && (int)best[u].size() == K) break;
    if ((int)best[u].size() > K) continue;
    for (auto [v, w] : adj[u]) {
        if ((int)best[v].size() < K)
            pq.push({d + w, v});
    }
}

Gotcha. This is NOT the same as standard Dijkstra's "skip if d > dist[v]" check. Here we allow multiple arrivals at the same node because we want the \(K\) best, not just the best. The guard best[v].size() < K prevents unbounded expansion.

Why K Shortest Paths Works

Standard Dijkstra pops nodes in cost order. The first time you pop node \(v\), you have its shortest distance. The second time, you have its second-shortest. The \(k\)-th time, its \(k\)-th shortest.

Normally we skip repeated pops as "stale." For \(K\) shortest paths, we allow the first \(K\) pops. Each pop is guaranteed to be the next-best distance because the priority queue maintains global cost ordering.

Complexity: \(O(K \cdot (N + M) \log(KN))\). Each node is popped at most \(K\) times, and each pop may push edges.

The General Pattern: Tuple Distances

Whenever you need to optimize multiple criteria simultaneously, encode your distance as a tuple and compare lexicographically.

Criteria Tuple Comparison
Min cost, then max value (cost, \(-\)value) Standard \(<\)
Min hops, then min weight (hops, weight) Standard \(<\)
Min cost, count paths (cost, count) \(<\) resets count; \(=\) adds count
K best costs sorted vector of size K Accept first K arrivals

The tuple approach works with both Floyd-Warshall and Dijkstra. Floyd uses tuple comparison in the relaxation. Dijkstra uses it in the priority queue or in the update logic.

Key insight. Multi-criteria optimization is not a new algorithm. It's a new data type for your distance table. The algorithm stays the same --- only the comparison and update rules change.

Exercises

  1. Three criteria. You want (min cost, max value, min hops) in that priority. Write the comparison operator.

  2. K = 1 equivalence. Show that the K shortest paths algorithm with \(K = 1\) produces exactly the same result as standard Dijkstra.

  3. Negative values. In the souvenir problem, what if some cities have negative souvenir values (penalties)? Does the Floyd-Warshall approach still work? Why?

Problems

Problem Link Difficulty
ABC286-E — Souvenir atcoder.jp/contests/abc286/tasks/abc286_e Medium
CSES — Investigation cses.fi/problemset/task/1202 Medium
CSES — Flight Routes cses.fi/problemset/task/1196 Hard