Algorithm Design Expert

Meridian Logistics: Nearest In-Stock Warehouse Under Dynamic Traffic

1. Problem Restatement

Model. A directed graph G = (V, E) has N nodes and M edges with positive integer weights that change over time. There are W warehouses, each fixed to a node. stock[w][sku] is a mutable non-negative integer. For each QUERY(s, k), return:

argmin over warehouses w with stock[w][k] ≥ 1 and d(s, node(w)) < ∞, ordered lexicographically by (d(s, node(w)), w). If no such warehouse exists, return −1.

Distances are forward (order node → warehouse) and must reflect every earlier event in the stream.

Assumptions

These points were not fully pinned down by the spec, so I made explicit choices:

Edge cases the solution must handle

• The order node cannot reach any stocked warehouse.
• A weight decrease shortens paths to several warehouses at once.
• A weight increase dethrones the current best warehouse, which may still be reachable another way.
• Ties on distance go to the smallest id.
• Zero stock (from the initial input or driven there by events) excludes a warehouse.
• A STOCK_CHANGE on a never-seen (warehouse, sku) pair starts from an implicit 0.
• The order node is itself a warehouse node (distance 0).
• Self-loops and parallel edges.
• Repeated updates to the same edge before a query.
• Bursts of queries with no intervening updates.
• A QUERY as the very first event.

A key structural observation

Edges are never inserted or deleted, and every weight stays in [1, ∞). So reachability is static, even though distances are dynamic. We can precompute, per strongly connected component (SCC), the set of warehouses it can reach, stored as a W-bit bitset.

The query "is any in-stock warehouse for this SKU reachable?" then becomes an AND of two 2000-bit bitsets, which takes 32 machine words. The same test prunes the search at every SCC boundary.

2. Candidate Approaches

Approach 0 – Full Dijkstra per query (baseline)

• Idea: Run a forward Dijkstra from the order node over the whole graph, then scan the warehouses.
• Time: O(Q·(N+M) log N), about 10⁵ × 7·10⁵ × 18 ≈ 10¹². Space: O(N+M).
• Trade-off: Trivially correct, hopeless at scale. Kept as the test oracle (--brute).

Approach 1 – Per-warehouse distance vectors with dynamic repair

• Idea: Run a reverse Dijkstra from each warehouse, then answer a query by min over warehouses of dist_w[s].
• Time: preprocessing O(W·(N+M) log N) ≈ 1.4·10⁹·log. Space: O(W·N) = 4·10⁸ entries ≈ 1.6 GB.
• Trade-off: Fails the 512 MB limit. Every traffic update would also have to repair up to W trees. Rejected.

Approach 2 – Early-terminating forward Dijkstra + static reachability pruning

• Idea:
  • Pre-check with the SCC bitset: if no in-stock warehouse is reachable, answer −1 in O(W/64). If exactly one is reachable, return it directly with no search, since the argmin over a single candidate is trivial.
  • Otherwise run Dijkstra from s. Stop as soon as the popped distance exceeds the first in-stock warehouse distance found (draining ties first), and never enter SCCs that cannot reach an in-stock warehouse for this SKU.
• Time:
  • Update: O(log deg + parallel copies).
  • Query: O(W/64 + |E_r| log |V_r|), where r is the distance to the answer and E_r, V_r are the edges and nodes within the Dijkstra ball of that radius.
  • Worst case is still O((N+M) log N) per query.
• Space: O(N+M + C·W/64 + S·W/64), where C is the SCC count and S the SKU count. About 60–70 MB in the worst case.
• Trade-off: Zero maintenance cost and excellent when stock is dense near customers. It degrades when the nearest stocked warehouse is far and the same SKU is queried repeatedly.

Approach 3 – Per-SKU nearest-warehouse field with Ramalingam–Reps repair

• Idea: For a SKU k, run a multi-source Dijkstra on the reversed graph from all nodes holding in-stock warehouses of k.
  • Labels are lexicographic pairs (dist, wid). Relaxation (d, w) ↦ (d + c, w) is strictly monotone, so Dijkstra computes, for every node x, min_w (d(x, w), w). This is exactly the tie-broken answer, and it makes a query an O(1) lookup.
  • Keep the shortest-path forest (a parent pointer per node) and repair it on each change:
    • Weight decrease or source gained / better id: start from the improved node and run a Dijkstra that only propagates strict improvements. Cost is proportional to the region whose labels change.
    • Weight increase on a tree edge or source lost: collect the affected subtree via parent pointers, reset it, re-seed it from its unaffected successors, and run Dijkstra inside it. A non-tree edge increase costs O(1).
    • Stock changes that do not flip 0 ↔ positive cost nothing.
• Time:
  • Build: O((N+M) log N).
  • Query hit: O(1).
  • Update: O(Σ over cached fields of affected-region size × log), worst case O((N+M) log N) per field.
• Space: 10 bytes × N per cached field (u32 dist, u16 wid, i32 parent), about 2 MB at N = 2·10⁵.
• Trade-off: Superb for hot SKUs. It is wasteful for cold SKUs, and cost multiplies with the number of cached fields on every traffic update.

Approach 4 – Customizable Contraction Hierarchies (CCH) + POI buckets

• Idea: Build a metric-independent nested-dissection ordering once.
  • Weight updates trigger partial re-customization of the shortcut weights they touch.
  • Nearest-POI queries use per-SKU bucket lists attached to the upward search space (Dibbelt–Strasser–Wagner customizable CH; Geisberger-style POI/one-to-many queries).
• Time: Queries run in microseconds on road-like graphs. An update costs the affected shortcut cone, typically thousands of operations.
• Space: O(M · shortcut factor).
• Trade-off: Best at 10× scale on road networks. The guarantees are empirical and depend on small separators. It is also complex, and per-SKU buckets must be updated on stock flips.

Comparison

Recommendation: an adaptive hybrid of 2 and 3

1. Always: use the O(W/64) SCC-bitset prefilter. Unreachable returns −1; a single candidate is returned directly.
2. Cold SKUs: answer with the bounded search (Approach 2) and charge its work ("rent") to the SKU.
3. Admission (ski rental): when a SKU's accumulated search work reaches the cost of one full field build (≈ N + M), build its field and serve O(1) lookups from then on. By the classical break-even argument, total cost is within 2× (up to log factors) of the better of "never cache" and "cache immediately".
4. Eviction (reverse ski rental): each field accumulates the repair work spent since its last hit. If that exceeds one rebuild, the field is evicted, so a field that isn't being queried can't burn unbounded update time. An LRU policy caps memory (≈160 MB of fields).
5. Lazy, coalesced traffic:
   • An update only records the edge's pre-change weight.
   • Repairs run at the next query or stock event that touches a field.
   • Five consecutive updates to one edge cost one repair, and an edge that returns to its old weight costs zero.
   • If no fields are cached, updates are O(log deg) and nothing more.

Honest limit. Fully dynamic shortest paths carry conditional lower bounds. Henzinger–Krinninger–Nanongkai–Saranurak (STOC 2015, OMv conjecture) show that dynamic s-t shortest path cannot have both update and query time polynomially below the trivial bounds. Our problem contains distance-comparison queries of this kind: place two warehouses and ask which one is closer.

So there is no provable guarantee against a fully adversarial stream. An example is alternating an update on an edge near two competing warehouses with a query from far upstream, on a long path. The hybrid adapts to the typical case and degrades to Approach 2's cost otherwise.

3. Implementation (C++17)

/**
 * meridian.cpp — Nearest in-stock warehouse under dynamic directed edge weights.
 *
 * Build: g++ -O2 -std=c++17 -o meridian meridian.cpp
 * Run:   ./meridian [--brute | --force-fields] [--max-fields=K] < input
 *
 * Complexity (N nodes, M edges, P <= M distinct (u,v) pairs, W warehouses,
 *             C SCCs, S SKUs, F cached fields, w64 = ceil(W/64)):
 *   Preprocess : O(M log M) CSR build + O(N+M) Tarjan + O(M * w64) reach bitsets.
 *   TRAFFIC    : O(log deg(u) + #parallel copies); repair deferred (lazy, coalesced).
 *   STOCK      : O(1) expected; if the in-stock flag flips and SKU k has a cached
 *                field, one Ramalingam–Reps repair: O(|affected| * log N).
 *   QUERY      : O(w64) prefilter; cached field => O(1) after flushing pending
 *                repairs; otherwise bounded Dijkstra O(|ball| log |ball|), pruned
 *                to SCCs that can reach an in-stock warehouse.
 *   Flush      : per effectively-changed pair, per cached field: O(|affected| log N)
 *                (non-tree edge increase: O(1)).
 *   Worst case : O((N+M) log N) per event (see OMv lower bound; unavoidable in general).
 *   Space      : O(N + M + C*w64 + S*w64 + F*10N bytes)  (~260 MB worst at limits).
 */
#include <bits/stdc++.h>
using namespace std;

namespace meridian {

using u32 = uint32_t;
using u64 = uint64_t;
using i64 = long long;

constexpr u32 INF_DIST = numeric_limits<u32>::max();
constexpr u64 INF_LABEL = numeric_limits<u64>::max();
constexpr uint16_t NO_WAREHOUSE = numeric_limits<uint16_t>::max();
constexpr int PARENT_SOURCE = -1;   // label comes from a warehouse at this node
constexpr int PARENT_NONE = -2;     // node cannot reach any in-stock warehouse
constexpr size_t kFieldMemoryBudget = 160u << 20;  // bytes for cached SKU fields

// Lexicographic (distance, warehouse id) packed so that integer order == label order.
inline u64 packLabel(u32 dist, u32 wid) { return (u64(dist) << 16) | wid; }

// =============================== Input =====================================
class Scanner {
public:
    Scanner() {
        static char chunk[1 << 16];
        size_t got;
        while ((got = fread(chunk, 1, sizeof chunk, stdin)) > 0) data_.append(chunk, got);
    }
    bool next(string_view& tok) {
        while (pos_ < data_.size() && isspace((unsigned char)data_[pos_])) ++pos_;
        if (pos_ >= data_.size()) return false;
        size_t start = pos_;
        while (pos_ < data_.size() && !isspace((unsigned char)data_[pos_])) ++pos_;
        tok = string_view(data_).substr(start, pos_ - start);
        return true;
    }
    bool peek(string_view& tok) { size_t save = pos_; bool ok = next(tok); pos_ = save; return ok; }
    string_view need() {
        string_view t;
        if (!next(t)) throw runtime_error("unexpected end of input");
        return t;
    }
    i64 nextInt() { return toInt(need()); }

    static bool isInt(string_view t) {
        size_t i = (!t.empty() && (t[0] == '-' || t[0] == '+')) ? 1 : 0;
        if (i >= t.size()) return false;
        for (; i < t.size(); ++i) if (t[i] < '0' || t[i] > '9') return false;
        return true;
    }
    static i64 toInt(string_view t) {
        if (!isInt(t)) throw runtime_error("expected integer, got '" + string(t) + "'");
        bool neg = t[0] == '-';
        size_t i = (t[0] == '-' || t[0] == '+') ? 1 : 0;
        i64 v = 0;
        for (; i < t.size(); ++i) v = v * 10 + (t[i] - '0');
        return neg ? -v : v;
    }
private:
    string data_;
    size_t pos_ = 0;
};

// =============================== Graph =====================================
enum class ParallelEdgePolicy { UpdateFirstListedCopy, UpdateAllCopies };
constexpr ParallelEdgePolicy kParallelPolicy = ParallelEdgePolicy::UpdateFirstListedCopy;

struct RawEdge { int u, v; u32 w; };

/** CSR with one entry per distinct (u,v), u != v. Pair id == forward CSR position. */
class RoadGraph {
public:
    int n = 0;
    vector<int> fwdStart, fwdTo, fwdFrom;   // forward CSR, targets sorted per source
    vector<u32> effW;                       // effective weight = min over parallel copies
    vector<int> copyStart;                  // copies of pair p: copyW[copyStart[p] .. copyStart[p+1])
    vector<u32> copyW;                      // in input order (first-listed copy first)
    vector<int> revStart, revFrom, revPair; // reverse CSR (shares weights through revPair)

    RoadGraph() = default;
    RoadGraph(int nodes, vector<RawEdge> edges) : n(nodes) {
        // Self-loops never shorten a path with positive weights: drop them.
        edges.erase(remove_if(edges.begin(), edges.end(),
                              [](const RawEdge& e) { return e.u == e.v; }), edges.end());
        // stable: parallel copies keep input order, so "first-listed copy" is well defined.
        stable_sort(edges.begin(), edges.end(), [](const RawEdge& a, const RawEdge& b) {
            return a.u != b.u ? a.u < b.u : a.v < b.v;
        });
        fwdStart.assign(n + 1, 0);
        for (size_t i = 0; i < edges.size(); ++i) {
            const RawEdge& e = edges[i];
            bool fresh = i == 0 || edges[i - 1].u != e.u || edges[i - 1].v != e.v;
            if (fresh) {
                fwdTo.push_back(e.v);
                fwdFrom.push_back(e.u);
                effW.push_back(e.w);
                copyStart.push_back((int)copyW.size());
                ++fwdStart[e.u + 1];
            } else {
                effW.back() = min(effW.back(), e.w);
            }
            copyW.push_back(e.w);
        }
        copyStart.push_back((int)copyW.size());
        for (int i = 0; i < n; ++i) fwdStart[i + 1] += fwdStart[i];

        const int P = pairs();
        revStart.assign(n + 1, 0);
        for (int p = 0; p < P; ++p) ++revStart[fwdTo[p] + 1];
        for (int i = 0; i < n; ++i) revStart[i + 1] += revStart[i];
        revFrom.resize(P);
        revPair.resize(P);
        vector<int> cursor(revStart.begin(), revStart.end() - 1);
        for (int p = 0; p < P; ++p) {
            int slot = cursor[fwdTo[p]]++;
            revFrom[slot] = fwdFrom[p];
            revPair[slot] = p;
        }
    }
    int pairs() const { return (int)fwdTo.size(); }

    int findPair(int u, int v) const {
        auto b = fwdTo.begin() + fwdStart[u], e = fwdTo.begin() + fwdStart[u + 1];
        auto it = lower_bound(b, e, v);
        return (it != e && *it == v) ? int(it - fwdTo.begin()) : -1;
    }

    /** Applies the update to the copy array; returns the NEW effective weight
     *  (caller decides what to do with effW, enabling lazy repair). */
    u32 applyCopyUpdate(int p, u32 w) {
        int b = copyStart[p], e = copyStart[p + 1];
        if (kParallelPolicy == ParallelEdgePolicy::UpdateAllCopies)
            for (int i = b; i < e; ++i) copyW[i] = w;
        else
            copyW[b] = w;
        u32 m = copyW[b];
        for (int i = b + 1; i < e; ++i) m = min(m, copyW[i]);
        return m;
    }
};

// =============================== Stock =====================================
class StockLedger {
public:
    int W = 0, words = 0;
    vector<int> whNode;                    // warehouse -> node
    vector<int> nodeWhStart, nodeWhList;   // node -> warehouses (ascending id)
    vector<int> warehouseNodes;            // distinct nodes that host >= 1 warehouse
    vector<u64> inStock;                   // [sku][words] bitset: qty > 0
    vector<int> inCount;                   // #warehouses with qty > 0, per sku

    void begin(int warehouses) {
        if (warehouses >= NO_WAREHOUSE) throw runtime_error("W too large for 16-bit ids");
        W = warehouses;
        words = (W + 63) / 64;
        whNode.assign(W, 0);
    }
    void finalize(int n) {
        nodeWhStart.assign(n + 1, 0);
        for (int w = 0; w < W; ++w) ++nodeWhStart[whNode[w] + 1];
        for (int i = 0; i < n; ++i) nodeWhStart[i + 1] += nodeWhStart[i];
        nodeWhList.resize(W);
        vector<int> cursor(nodeWhStart.begin(), nodeWhStart.end() - 1);
        for (int w = 0; w < W; ++w) nodeWhList[cursor[whNode[w]]++] = w;  // ascending ids
        for (int v = 0; v < n; ++v)
            if (nodeWhStart[v + 1] > nodeWhStart[v]) warehouseNodes.push_back(v);
    }

    int lookup(string_view tok) const {
        auto it = ids_.find(string(tok));
        return it == ids_.end() ? -1 : it->second;
    }
    int getOrCreate(string_view tok) {
        auto [it, inserted] = ids_.try_emplace(string(tok), (int)inCount.size());
        if (inserted) {  // implicit quantity 0 everywhere
            inCount.push_back(0);
            inStock.resize(inStock.size() + words, 0);
        }
        return it->second;
    }
    int numSkus() const { return (int)inCount.size(); }
    const u64* row(int sku) const { return inStock.data() + size_t(sku) * words; }
    bool has(int sku, int wid) const {
        return (inStock[size_t(sku) * words + (wid >> 6)] >> (wid & 63)) & 1ULL;
    }

    /** Applies delta; returns true iff the (sku, wid) in-stock flag flipped. */
    bool adjust(int sku, int wid, i64 delta) {
        u64 key = u64(sku) * u64(W) + u64(wid);
        auto it = qty_.find(key);
        i64 before = it == qty_.end() ? 0 : it->second;
        i64 after = max<i64>(0, before + delta);  // defensive; upstream guarantees >= 0
        if (after == 0) { if (it != qty_.end()) qty_.erase(it); }
        else if (it == qty_.end()) qty_.emplace(key, after);
        else it->second = after;
        bool was = before > 0, now = after > 0;
        if (was == now) return false;
        inStock[size_t(sku) * words + (wid >> 6)] ^= (1ULL << (wid & 63));
        inCount[sku] += now ? 1 : -1;
        return true;
    }

    /** Smallest in-stock warehouse id at `node` for `sku`, or NO_WAREHOUSE. */
    uint16_t sourceWid(int node, int sku) const {
        for (int i = nodeWhStart[node]; i < nodeWhStart[node + 1]; ++i)
            if (has(sku, nodeWhList[i])) return (uint16_t)nodeWhList[i];
        return NO_WAREHOUSE;
    }
private:
    unordered_map<string, int> ids_;
    unordered_map<u64, i64> qty_;
};

// =============================== Engine ====================================
struct Config {
    enum class Mode { Adaptive, ForceFields, BruteForce } mode = Mode::Adaptive;
    int maxFields = 0;  // 0 = derive from memory budget
};

class Engine {
public:
    Engine(RoadGraph graph, StockLedger ledger, Config cfg)
        : g_(move(graph)), s_(move(ledger)), cfg_(cfg), n_(g_.n) {
        dirtyFlag_.assign(g_.pairs(), 0);
        dirtyOld_.assign(g_.pairs(), 0);
        inAffected_.assign(n_, 0);
        sDist_.assign(n_, 0);
        sStamp_.assign(n_, 0);
        computeScc();
        computeReach();
        compStamp_.assign(numComp_, 0);
        compOk_.assign(numComp_, 0);

        rebuildCost_ = i64(n_) + g_.pairs() + 1;
        admitThreshold_ = rebuildCost_;
        evictThreshold_ = cfg_.mode == Config::Mode::ForceFields
                              ? numeric_limits<i64>::max() : rebuildCost_;
        size_t perField = max<size_t>(1, size_t(n_) * (sizeof(u32) + sizeof(uint16_t) + sizeof(int)));
        maxFields_ = cfg_.maxFields > 0 ? cfg_.maxFields
                   : (int)clamp<size_t>(kFieldMemoryBudget / perField, 1, 256);
        syncSkuTables();
    }

    // ---------------------------- TRAFFIC ----------------------------------
    void onTraffic(i64 u, i64 v, i64 w) {
        if (u < 0 || u >= n_ || v < 0 || v >= n_) return;
        if (w <= 0 || w >= (i64)INF_DIST) { cerr << "warning: ignoring weight " << w << "\n"; return; }
        if (u == v) return;                          // self-loop: never on a shortest path
        int p = g_.findPair((int)u, (int)v);
        if (p < 0) return;                           // spec guarantees existence
        u32 newEff = g_.applyCopyUpdate(p, (u32)w);
        if (newEff == g_.effW[p]) return;            // e.g. a non-minimal parallel copy changed
        // Lazy: remember the weight the cached fields were built against; repair later.
        if (activeFields_ > 0 && !dirtyFlag_[p]) {
            dirtyFlag_[p] = 1;
            dirtyOld_[p] = g_.effW[p];
            dirty_.push_back(p);
        }
        g_.effW[p] = newEff;                         // bounded search always sees truth
    }

    // ----------------------------- STOCK -----------------------------------
    void onStock(i64 wid, string_view skuTok, i64 delta) {
        if (wid < 0 || wid >= s_.W) return;
        int sku = s_.getOrCreate(skuTok);            // handles never-before-stocked SKUs
        syncSkuTables();
        if (!s_.adjust(sku, (int)wid, delta)) return;  // flag unchanged: nothing to repair
        if (cfg_.mode == Config::Mode::BruteForce) return;
        if (fieldOf_[sku] < 0) return;
        flushTraffic(sku);                           // field must match current weights first
        Field& f = fields_[fieldOf_[sku]];
        i64 work = 0;
        applySourceChange(f, s_.whNode[wid], work);
        f.rent += work;
    }

    // ----------------------------- QUERY -----------------------------------
    int onQuery(i64 nodeIn, string_view skuTok) {
        if (nodeIn < 0 || nodeIn >= n_) return -1;
        const int node = (int)nodeIn;
        const int sku = s_.lookup(skuTok);
        if (sku < 0) return -1;                      // SKU never seen => no stock anywhere
        if (cfg_.mode == Config::Mode::BruteForce) return bruteForce(node, sku);
        if (s_.inCount[sku] == 0) return -1;

        // Static reachability filter (weights change, reachability never does).
        int only = -1;
        int candidates = reachableInStock(comp_[node], sku, only);
        if (candidates == 0) return -1;              // unreachable component: O(W/64)
        if (candidates == 1) return only;            // single candidate is trivially optimal

        if (fieldOf_[sku] < 0 && cfg_.mode == Config::Mode::ForceFields) {
            flushTraffic(-1);
            admit(sku);
        }
        if (fieldOf_[sku] >= 0) {                    // hot SKU: O(1) after pending repairs
            flushTraffic(sku);
            Field& f = fields_[fieldOf_[sku]];
            f.rent = 0;
            f.lastUsed = ++clock_;
            return f.dist[node] == INF_DIST ? -1 : int(f.wid[node]);
        }
        i64 work = 0;
        int answer = boundedSearch(node, sku, work);
        searchWork_[sku] += work;
        if (searchWork_[sku] >= admitThreshold_) {   // ski rental: rent paid >= buy price
            flushTraffic(-1);
            admit(sku);
        }
        return answer;
    }

private:
    /** Nearest-warehouse field of one SKU over the reversed graph. */
    struct Field {
        int sku = -1;              // -1 = free slot
        vector<u32> dist;          // distance to nearest in-stock warehouse
        vector<uint16_t> wid;      // its id (tie-broken)
        vector<int> parent;        // next hop toward it, or PARENT_SOURCE / PARENT_NONE
        i64 rent = 0;              // repair work since last hit
        u64 lastUsed = 0;
    };

    RoadGraph g_;
    StockLedger s_;
    Config cfg_;
    int n_;

    // Static reachability: SCC id per node, per-SCC bitset of reachable warehouses.
    vector<int> comp_;
    int numComp_ = 0;
    vector<u64> reach_;

    // Lazy traffic repair.
    vector<int> dirty_;
    vector<char> dirtyFlag_;
    vector<u32> dirtyOld_;
    vector<pair<int, u32>> pending_;

    // Field cache.
    vector<Field> fields_;
    vector<int> fieldOf_;          // sku -> slot or -1
    vector<i64> searchWork_;       // sku -> accumulated bounded-search work
    int activeFields_ = 0, maxFields_ = 1;
    u64 clock_ = 0;
    i64 rebuildCost_ = 0, admitThreshold_ = 0, evictThreshold_ = 0;

    // Scratch.
    vector<pair<u64, int>> fheap_, sheap_;
    vector<char> inAffected_;
    vector<int> affected_;
    vector<u64> sDist_;
    vector<u32> sStamp_, compStamp_;
    vector<char> compOk_;
    u32 stamp_ = 0;

    static constexpr greater<pair<u64, int>> kMinHeap{};

    void syncSkuTables() {
        size_t k = s_.numSkus();
        if (fieldOf_.size() < k) { fieldOf_.resize(k, -1); searchWork_.resize(k, 0); }
    }

    // ------------------------ static reachability ---------------------------
    void computeScc() {  // iterative Tarjan; SCC ids come out in reverse topological order
        comp_.assign(n_, -1);
        vector<int> idx(n_, -1), low(n_, 0), stk;
        vector<char> onStk(n_, 0);
        vector<pair<int, int>> call;  // (node, next forward edge position)
        int counter = 0;
        for (int s = 0; s < n_; ++s) {
            if (idx[s] != -1) continue;
            idx[s] = low[s] = counter++;
            stk.push_back(s); onStk[s] = 1;
            call.emplace_back(s, g_.fwdStart[s]);
            while (!call.empty()) {
                int v = call.back().first;
                int& it = call.back().second;
                if (it < g_.fwdStart[v + 1]) {
                    int w = g_.fwdTo[it++];                 // advance before any push_back
                    if (idx[w] == -1) {
                        idx[w] = low[w] = counter++;
                        stk.push_back(w); onStk[w] = 1;
                        call.emplace_back(w, g_.fwdStart[w]);
                    } else if (onStk[w]) {
                        low[v] = min(low[v], idx[w]);
                    }
                } else {
                    if (low[v] == idx[v]) {
                        int x;
                        do { x = stk.back(); stk.pop_back(); onStk[x] = 0; comp_[x] = numComp_; }
                        while (x != v);
                        ++numComp_;
                    }
                    call.pop_back();
                    if (!call.empty()) {
                        int par = call.back().first;
                        low[par] = min(low[par], low[v]);
                    }
                }
            }
        }
    }

    void computeReach() {
        const int words = s_.words;
        reach_.assign(size_t(numComp_) * words, 0);
        if (words == 0) return;
        vector<int> start(numComp_ + 1, 0), order(n_);
        for (int v = 0; v < n_; ++v) ++start[comp_[v] + 1];
        for (int c = 0; c < numComp_; ++c) start[c + 1] += start[c];
        vector<int> cursor(start.begin(), start.end() - 1);
        for (int v = 0; v < n_; ++v) order[cursor[comp_[v]]++] = v;
        // Tarjan order: every cross edge goes from a higher SCC id to a lower one.
        for (int c = 0; c < numComp_; ++c) {
            u64* rc = &reach_[size_t(c) * words];
            for (int i = start[c]; i < start[c + 1]; ++i) {
                int v = order[i];
                for (int j = s_.nodeWhStart[v]; j < s_.nodeWhStart[v + 1]; ++j) {
                    int w = s_.nodeWhList[j];
                    rc[w >> 6] |= 1ULL << (w & 63);
                }
                for (int e = g_.fwdStart[v]; e < g_.fwdStart[v + 1]; ++e) {
                    int c2 = comp_[g_.fwdTo[e]];
                    if (c2 == c) continue;
                    const u64* r2 = &reach_[size_t(c2) * words];
                    for (int k = 0; k < words; ++k) rc[k] |= r2[k];
                }
            }
        }
    }

    /** Counts (capped at 2) warehouses reachable from SCC c that stock sku. */
    int reachableInStock(int c, int sku, int& only) const {
        const int words = s_.words;
        if (words == 0) return 0;
        const u64* a = &reach_[size_t(c) * words];
        const u64* b = s_.row(sku);
        int count = 0;
        for (int k = 0; k < words; ++k) {
            u64 x = a[k] & b[k];
            if (!x) continue;
            if (count == 0) only = k * 64 + __builtin_ctzll(x);
            count += __builtin_popcountll(x);
            if (count >= 2) return 2;
        }
        return count;
    }

    bool componentUseful(int c, int sku) {
        if (compStamp_[c] == stamp_) return compOk_[c];
        compStamp_[c] = stamp_;
        int dummy;
        return compOk_[c] = (reachableInStock(c, sku, dummy) > 0);
    }

    // ------------------ Approach 2: bounded forward Dijkstra ----------------
    int boundedSearch(int src, int sku, i64& work) {
        if (++stamp_ == 0) {  // wrap-around (practically unreachable)
            fill(sStamp_.begin(), sStamp_.end(), 0);
            fill(compStamp_.begin(), compStamp_.end(), 0);
            stamp_ = 1;
        }
        sheap_.clear();
        sStamp_[src] = stamp_;
        sDist_[src] = 0;
        sheap_.emplace_back(0, src);
        u64 bestDist = numeric_limits<u64>::max();
        int best = -1;
        while (!sheap_.empty()) {
            pop_heap(sheap_.begin(), sheap_.end(), kMinHeap);
            auto [d, x] = sheap_.back();
            sheap_.pop_back();
            if (d != sDist_[x]) continue;                 // stale entry
            if (best >= 0 && d > bestDist) break;          // all ties already drained
            ++work;
            uint16_t sw = s_.sourceWid(x, sku);
            if (sw != NO_WAREHOUSE && (best < 0 || sw < best)) { best = sw; bestDist = d; }
            if (best >= 0) continue;  // anything beyond bestDist cannot win; only drain ties
            for (int e = g_.fwdStart[x]; e < g_.fwdStart[x + 1]; ++e) {
                ++work;
                int y = g_.fwdTo[e];
                u64 nd = d + g_.effW[e];
                if (sStamp_[y] == stamp_ && nd >= sDist_[y]) continue;
                if (!componentUseful(comp_[y], sku)) continue;  // dead region for this SKU
                sStamp_[y] = stamp_;
                sDist_[y] = nd;
                sheap_.emplace_back(nd, y);
                push_heap(sheap_.begin(), sheap_.end(), kMinHeap);
            }
        }
        sheap_.clear();
        return best;
    }

    // ------------------ Approach 3: per-SKU fields + repair -----------------
    static u64 labelOf(const Field& f, int v) {
        return f.dist[v] == INF_DIST ? INF_LABEL : packLabel(f.dist[v], f.wid[v]);
    }
    void setLabel(Field& f, int v, u32 d, uint16_t w, int parent) {
        f.dist[v] = d; f.wid[v] = w; f.parent[v] = parent;
        fheap_.emplace_back(packLabel(d, w), v);
        push_heap(fheap_.begin(), fheap_.end(), kMinHeap);
    }

    /** Dijkstra on the reversed graph over lexicographic labels. Only strict
     *  improvements propagate, so this doubles as the repair engine. */
    void propagate(Field& f, i64& work) {
        while (!fheap_.empty()) {
            pop_heap(fheap_.begin(), fheap_.end(), kMinHeap);
            auto [key, y] = fheap_.back();
            fheap_.pop_back();
            if (key != labelOf(f, y)) continue;           // stale
            ++work;
            const u32 dy = f.dist[y];
            const uint16_t wy = f.wid[y];
            for (int e = g_.revStart[y]; e < g_.revStart[y + 1]; ++e) {
                ++work;
                int x = g_.revFrom[e];                    // forward edge x -> y
                u64 nd = u64(dy) + g_.effW[g_.revPair[e]];
                if (nd >= INF_DIST) continue;
                if (packLabel((u32)nd, wy) < labelOf(f, x)) setLabel(f, x, (u32)nd, wy, y);
            }
        }
    }

    void buildField(Field& f) {
        f.dist.assign(n_, INF_DIST);
        f.wid.assign(n_, NO_WAREHOUSE);
        f.parent.assign(n_, PARENT_NONE);
        for (int node : s_.warehouseNodes) {
            uint16_t sw = s_.sourceWid(node, f.sku);   // smallest in-stock id at this node
            if (sw != NO_WAREHOUSE) setLabel(f, node, 0, sw, PARENT_SOURCE);
        }
        i64 work = 0;
        propagate(f, work);
    }

    /** Edge x->y got cheaper: only x (and nodes upstream of it) can improve. */
    void relaxDecreasedEdge(Field& f, int x, int y, int p, i64& work) {
        if (f.dist[y] == INF_DIST) return;
        u64 nd = u64(f.dist[y]) + g_.effW[p];
        if (nd >= INF_DIST) return;
        if (packLabel((u32)nd, f.wid[y]) < labelOf(f, x)) {
            setLabel(f, x, (u32)nd, f.wid[y], y);
            propagate(f, work);
        }
    }

    /** Edge x->y got more expensive: only matters if it is x's tree edge. */
    void repairIncreasedEdge(Field& f, int x, int y, i64& work) {
        if (f.parent[x] != y) { ++work; return; }      // non-tree edge: O(1)
        repairSubtree(f, x, work);
    }

    /** Ramalingam–Reps style: reset the shortest-path subtree hanging off `seed`
     *  (all nodes whose tree path passes through seed), re-seed each from its own
     *  source or unaffected successors, then Dijkstra inside the region. */
    void repairSubtree(Field& f, int seed, i64& work) {
        affected_.clear();
        affected_.push_back(seed);
        inAffected_[seed] = 1;
        for (size_t i = 0; i < affected_.size(); ++i) {
            int z = affected_[i];
            for (int e = g_.revStart[z]; e < g_.revStart[z + 1]; ++e) {
                ++work;
                int x = g_.revFrom[e];
                if (!inAffected_[x] && f.parent[x] == z) { inAffected_[x] = 1; affected_.push_back(x); }
            }
        }
        for (int x : affected_) { f.dist[x] = INF_DIST; f.wid[x] = NO_WAREHOUSE; f.parent[x] = PARENT_NONE; }
        for (int x : affected_) {
            ++work;
            u64 best = INF_LABEL; u32 bd = 0; uint16_t bw = NO_WAREHOUSE; int bp = PARENT_NONE;
            uint16_t sw = s_.sourceWid(x, f.sku);
            if (sw != NO_WAREHOUSE) { best = packLabel(0, sw); bd = 0; bw = sw; bp = PARENT_SOURCE; }
            for (int e = g_.fwdStart[x]; e < g_.fwdStart[x + 1]; ++e) {
                ++work;
                int y = g_.fwdTo[e];
                if (inAffected_[y] || f.dist[y] == INF_DIST) continue;
                u64 nd = u64(f.dist[y]) + g_.effW[e];
                if (nd >= INF_DIST) continue;
                u64 cand = packLabel((u32)nd, f.wid[y]);
                if (cand < best) { best = cand; bd = (u32)nd; bw = f.wid[y]; bp = y; }
            }
            if (best != INF_LABEL) setLabel(f, x, bd, bw, bp);
        }
        for (int x : affected_) inAffected_[x] = 0;
        propagate(f, work);  // resolves dependencies among affected nodes
    }

    /** The smallest in-stock id at node p may have changed. */
    void applySourceChange(Field& f, int p, i64& work) {
        uint16_t sw = s_.sourceWid(p, f.sku);
        u64 newSource = sw == NO_WAREHOUSE ? INF_LABEL : packLabel(0, sw);
        u64 current = labelOf(f, p);
        if (f.parent[p] == PARENT_SOURCE) {
            if (newSource == current) return;
            if (newSource < current) { setLabel(f, p, 0, sw, PARENT_SOURCE); propagate(f, work); }
            else repairSubtree(f, p, work);            // source lost or worse id
        } else if (newSource < current) {              // new source (restock / first stock)
            setLabel(f, p, 0, sw, PARENT_SOURCE);
            propagate(f, work);
        }
    }

    /** Apply all deferred weight changes to every cached field, one edge at a
     *  time, so each repair starts from a field consistent with the graph. */
    void flushTraffic(int protectSku) {
        if (dirty_.empty()) return;
        if (activeFields_ == 0) {
            for (int p : dirty_) dirtyFlag_[p] = 0;
            dirty_.clear();
            return;
        }
        pending_.clear();
        for (int p : dirty_) {                         // roll back to what fields saw
            pending_.emplace_back(p, g_.effW[p]);
            g_.effW[p] = dirtyOld_[p];
            dirtyFlag_[p] = 0;
        }
        dirty_.clear();
        for (auto [p, newW] : pending_) {
            u32 oldW = g_.effW[p];
            if (newW == oldW) continue;                // coalesced back to original
            g_.effW[p] = newW;
            int x = g_.fwdFrom[p], y = g_.fwdTo[p];
            for (Field& f : fields_) {
                if (f.sku < 0) continue;
                i64 work = 0;
                if (newW < oldW) relaxDecreasedEdge(f, x, y, p, work);
                else repairIncreasedEdge(f, x, y, work);
                f.rent += work;
            }
        }
        for (int i = 0; i < (int)fields_.size(); ++i)   // reverse ski rental
            if (fields_[i].sku >= 0 && fields_[i].sku != protectSku && fields_[i].rent > evictThreshold_)
                evict(i);
    }

    void admit(int sku) {
        int slot = -1;
        for (int i = 0; i < (int)fields_.size(); ++i) if (fields_[i].sku < 0) { slot = i; break; }
        if (slot < 0) {
            if ((int)fields_.size() < maxFields_) { fields_.emplace_back(); slot = (int)fields_.size() - 1; }
            else {                                     // LRU eviction
                slot = 0;
                for (int i = 1; i < (int)fields_.size(); ++i)
                    if (fields_[i].lastUsed < fields_[slot].lastUsed) slot = i;
                evict(slot);
            }
        }
        Field& f = fields_[slot];
        f.sku = sku; f.rent = 0; f.lastUsed = ++clock_;
        buildField(f);
        fieldOf_[sku] = slot;
        ++activeFields_;
    }

    void evict(int slot) {
        Field& f = fields_[slot];
        fieldOf_[f.sku] = -1;
        searchWork_[f.sku] = 0;                        // must re-earn admission
        f.sku = -1;
        --activeFields_;                               // vectors kept for reuse
    }

    // ------------------------ oracle (tests only) ---------------------------
    int bruteForce(int src, int sku) {
        vector<u64> d(n_, numeric_limits<u64>::max());
        priority_queue<pair<u64, int>, vector<pair<u64, int>>, greater<>> pq;
        d[src] = 0; pq.emplace(0, src);
        while (!pq.empty()) {
            auto [du, u] = pq.top(); pq.pop();
            if (du != d[u]) continue;
            for (int e = g_.fwdStart[u]; e < g_.fwdStart[u + 1]; ++e) {
                int v = g_.fwdTo[e];
                if (du + g_.effW[e] < d[v]) { d[v] = du + g_.effW[e]; pq.emplace(d[v], v); }
            }
        }
        int best = -1; u64 bd = numeric_limits<u64>::max();
        for (int w = 0; w < s_.W; ++w) {
            u64 dw = d[s_.whNode[w]];
            if (s_.has(sku, w) && dw != numeric_limits<u64>::max() && dw < bd) { bd = dw; best = w; }
        }
        return best;
    }
};

}  // namespace meridian

int main(int argc, char** argv) {
    using namespace meridian;
    Config cfg;
    for (int i = 1; i < argc; ++i) {
        string a = argv[i];
        if (a == "--brute") cfg.mode = Config::Mode::BruteForce;
        else if (a == "--force-fields") cfg.mode = Config::Mode::ForceFields;
        else if (a.rfind("--max-fields=", 0) == 0) cfg.maxFields = stoi(a.substr(13));
    }
    try {
        Scanner in;
        string_view tok;
        if (!in.peek(tok)) return 0;
        const i64 N = in.nextInt(), M = in.nextInt(), W = in.nextInt();
        if (N < 0 || M < 0 || W < 0) throw runtime_error("negative header value");

        vector<RawEdge> edges;
        edges.reserve((size_t)M);
        for (i64 i = 0; i < M; ++i) {
            i64 u = in.nextInt(), v = in.nextInt(), w = in.nextInt();
            if (u < 0 || u >= N || v < 0 || v >= N || w <= 0 || w >= (i64)INF_DIST)
                throw runtime_error("invalid edge on input line " + to_string(i + 2));
            edges.push_back({(int)u, (int)v, (u32)w});
        }

        StockLedger ledger;
        ledger.begin((int)W);
        for (int w = 0; w < W; ++w) {
            i64 node = in.nextInt(), count = in.nextInt();
            if (node < 0 || node >= N || count < 0) throw runtime_error("invalid warehouse line");
            ledger.whNode[w] = (int)node;
            for (i64 k = 0; k < count; ++k) {
                string_view t = in.need();
                size_t colon = t.rfind(':');
                string_view sku = colon == string_view::npos ? t : t.substr(0, colon);
                string_view qs = colon == string_view::npos ? string_view() : t.substr(colon + 1);
                i64 qty = qs.empty() ? in.nextInt() : Scanner::toInt(qs);
                int id = ledger.getOrCreate(sku);
                if (qty > 0) ledger.adjust(id, w, qty);  // duplicates are summed
            }
        }
        ledger.finalize((int)N);
        if (in.peek(tok) && Scanner::isInt(tok)) in.next(tok);  // optional event count

        Engine engine(RoadGraph((int)N, move(edges)), move(ledger), cfg);
        string out;
        out.reserve(1 << 20);
        while (in.next(tok)) {
            char type = (char)toupper((unsigned char)tok[0]);
            if (type == 'T') {
                i64 u = in.nextInt(), v = in.nextInt(), w = in.nextInt();
                engine.onTraffic(u, v, w);
            } else if (type == 'S') {
                i64 wid = in.nextInt();
                string_view sku = in.need();
                i64 delta = in.nextInt();
                engine.onStock(wid, sku, delta);
            } else if (type == 'Q') {
                i64 node = in.nextInt();
                string_view sku = in.need();
                out += to_string(engine.onQuery(node, sku));
                out += '\n';
            } else {
                throw runtime_error("unknown event '" + string(tok) + "'");
            }
        }
        fwrite(out.data(), 1, out.size(), stdout);
    } catch (const exception& e) {
        cerr << "error: " << e.what() << "\n";
        return 1;
    }
    return 0;
}

Correctness notes on non-obvious steps

• Lexicographic labels. (d, w) ↦ (d + c, w) preserves strict order for c ≥ 1. Dijkstra therefore settles every node at min_w (d(x, w), w), which is exactly the required tie-break.
• Parent forest is acyclic. parent[x] = y implies dist[x] = dist[y] + c > dist[y].
• Increase repair only touches the subtree. A node whose tree path avoids the changed edge (or lost source) still has a path of equal cost. Nothing can get cheaper after an increase, so its label is unchanged.
• Lazy flush is consistent. Dirty pairs are rolled back to the weights the fields last saw, then re-applied one at a time. Each repair therefore starts from a field that is exactly correct for the current intermediate graph.

4. Test Cases

T1 — Mixed functional test

This covers ties, stock-outs, restocks, a new SKU, self-loops, parallel edges, the order node being a warehouse, unreachable nodes, an unknown SKU, and a query as the first event.

5 6 3
0 1 5
0 2 5
0 0 3
2 4 1
0 4 20
0 4 7
2 1 100:1
1 1 100:2
4 2 100:5 200:1
Q 0 100
S 0 100 -1
Q 0 100
T 0 1 9
Q 0 100
Q 0 200
Q 3 100
Q 2 100
S 0 100 3
Q 2 100
S 1 300 4
Q 0 300
Q 4 300
Q 0 999
T 0 4 1
T 0 1 1
Q 0 100

Expected output:

0
1
2
2
-1
2
0
1
-1
-1
1

T2 — Increase with an alternate path (stale-cache test)

4 4 2
0 1 1
1 3 1
0 2 5
2 3 5
3 1 7:1
2 1 7:1
Q 0 7
T 1 3 10000
Q 0 7
S 1 7 -1
Q 0 7
T 0 2 10000
Q 0 7

Expected output: 0 1 0 0.

• Increase on a tree edge makes W1 (distance 5) better than W0 (now distance 10).
• W0 is still reachable via the other path.
• A second increase flips the best route back through node 1 (distance 10001).

T3 — Parallel-edge minimum and redundant updates

3 3 2
0 1 10
0 1 3
0 2 2
1 1 5:1
2 1 5:1
Q 0 5
T 0 1 20
Q 0 5
T 0 1 1
Q 0 5

Expected output: 1 1 0.

• Effective weight of (0, 1) is 3.
• The update sets the first-listed copy to 20; the effective weight stays 3, so the no-op is detected.
• The update to 1 makes the effective weight 1.

T4 — Adversarial and scale tests

These are generated rather than hand-written:

T5 — Randomized differential test (all modes vs. brute force)

gen.py produces small random instances that respect the spec's no-negative-stock guarantee:

# gen.py — small random instances (spec-valid: stock never goes negative)
import random, sys
random.seed(int(sys.argv[1]))
n = random.randint(1, 8); W = random.randint(0, 4)
edges = [(random.randrange(n), random.randrange(n), random.randint(1, 5))
         for _ in range(random.randint(0, 20))]
skus = ["1", "2", "3"]; qty = {}
print(n, len(edges), W)
for e in edges: print(*e)
for w in range(W):
    pairs = []
    for _ in range(random.randint(0, 3)):
        s, q = random.choice(skus), random.randint(0, 2)
        qty[(w, s)] = qty.get((w, s), 0) + q; pairs.append(f"{s}:{q}")
    print(random.randrange(n), len(pairs), *pairs)
ev = []
for _ in range(random.randint(1, 80)):
    r = random.random()
    if r < 0.35 and edges:
        u, v, _ = random.choice(edges); ev.append(f"T {u} {v} {random.randint(1, 5)}")
    elif r < 0.6 and W:
        w, s = random.randrange(W), random.choice(skus + ["9"])
        d = random.choice([-1, 1, 2]) if qty.get((w, s), 0) > 0 else random.choice([1, 2])
        qty[(w, s)] = qty.get((w, s), 0) + d; ev.append(f"S {w} {s} {d}")
    else:
        ev.append(f"Q {random.randrange(n)} {random.choice(skus + ['9'])}")
print(len(ev)); print("\n".join(ev))

Run the three modes against each other on many seeds:

g++ -O2 -std=c++17 -fsanitize=address,undefined -o meridian meridian.cpp
for s in $(seq 1 20000); do
  python3 gen.py $s > in.txt
  ./meridian --brute < in.txt > a.txt
  ./meridian < in.txt > b.txt
  ./meridian --force-fields < in.txt > c.txt
  ./meridian --force-fields --max-fields=1 < in.txt > d.txt   # constant LRU eviction
  cmp -s a.txt b.txt && cmp -s a.txt c.txt && cmp -s a.txt d.txt || { echo "MISMATCH seed $s"; break; }
done

--force-fields sends every multi-candidate query through the field and repair path. --max-fields=1 also exercises eviction and rebuild.

I have not executed these tests in this session. Expected outputs for T1–T3 were derived by hand. Please run the harness (under sanitizers) before production use.

5. Optimization Notes

Already applied

• Static SCC reachability bitsets. Instant −1 answers, a direct answer when only one candidate exists, and pruning of dead regions during search.
• Lazy, coalesced repairs. Repeated updates to the same edge cost one repair, and an update that changes a non-minimal parallel copy costs nothing.
• Ski-rental admission and eviction. Per SKU, the combined search and repair cost stays within about 2× (up to log factors) of the better of pure search and pure caching.
• Early termination with tie draining in the bounded search.
• CSR layouts and parallel-edge dedup, so the repair loop never scans duplicate edges.

Further speedups

1. Faster heap. Weights are ≤ 10⁴, so a radix heap or Dial-style bucket queue for the bounded search gives roughly 2–3× over a binary heap.
2. Goal-directed search. A* with ALT landmark lower bounds needs bounds that stay valid under updates. A safe choice uses the minimum weight each edge has ever had. They weaken if traffic dips occur.
3. Batched repair. Group dirty pairs per flush and run one multi-seed increase-then-decrease repair per field (Ramalingam–Reps batched), instead of one pass per edge.
4. Shift detection. When an increased tree edge's subtree has no alternative entry, all affected labels shift by the same Δ. Detecting this avoids a Dijkstra over the subtree.
5. Compact fields. Drop parent and recompute tree membership from dist equality to cut 40% of field memory, trading some repair speed.
6. Parallelism. Repairs of different fields are independent, so a flush can be parallelized per field.

Lower bounds

• Trivial: Ω(1) per event plus input size.
• Conditional: under the OMv conjecture (Henzinger–Krinninger–Nanongkai–Saranurak, 2015), dynamic s-t shortest paths cannot have both update and query time polynomially sublinear. Our problem can encode "which of two warehouses is closer" questions, so it inherits this barrier in the fully adversarial setting.

Practical speedups must therefore exploit structure, such as road-network separators, locality of traffic changes, or SKU popularity skew. Worst-case guarantees are not available.

10× scale (N = 2·10⁶, M = 5·10⁶, Q = 10⁶)

• Memory. About 20 MB per field means only around 10–20 fields fit. Reach bitsets could hit 2·10⁶ × 32 words ≈ 512 MB.
  • Compress reach to per-SCC-DAG-node storage only for SCCs with outgoing structure.
  • Road graphs usually have one giant SCC, so store the bitset per SCC with deduplication (hash-cons identical rows).
  • Widen warehouse ids beyond 16 bits if W grows past 65534.
• Switch the core to Customizable Contraction Hierarchies:
  • One-time metric-independent ordering via nested dissection, e.g. with InertialFlow or KaHIP.
  • A traffic update re-customizes only the shortcuts whose lower triangles contain the edge: milliseconds, not traversals.
  • Queries use upward searches plus per-SKU POI buckets. A stock flip inserts or removes one warehouse's backward search space into that SKU's buckets.
  • Queries typically land in the tens of microseconds, far below the sub-second target. It's the standard industrial answer on road networks.
• Engineering.
  • Batch updates per time window: apply all traffic in one partial re-customization.
  • Use a double-buffered metric so queries read a consistent snapshot while the next one is being built.
  • Partition by city region (sharding) with boundary-node overlays if a single machine is insufficient.
  • Use 32-bit distances with overflow checks (max path ≈ 2·10¹⁰ now exceeds u32, so switch dist to u64 or scale to seconds with explicit bounds).