The run of identical labels is not a property of a node. It is a property of how you arrived there. That is the entire problem: ordinary Dijkstra over `n` nodes has nowhere to keep "and the last three characters I passed were all `b`", so it cheerfully takes a cheap edge that only becomes illegal two hops later. My first instinct was to prune locally — refuse an edge when `labels[u] == labels[v]` and the current run already feels long. That collapses immediately, because a longer run can carry the cheaper tail. With `k = 3`, reaching a node on run 1 and reaching it on run 3 are two different futures and neither dominates the other, so you cannot throw either away. The fix is to stop filtering edges and put the run into the state instead. `k <= 50` is the permission slip: `(node, run)` is at most `5*10^4 * 50` = 2.5 million states, and the transitions add up to `k * |edges|`, also 2.5 million. Dijkstra over that graph needs nothing clever. I flattened the state to `v * k + (run - 1)`. Walking `v -> u` sets the new run to `run + 1` when the labels match and back to `1` when they differ; `new run > k` means the edge does not exist in the state graph at all. The start is `(0, 1)`, legal for free since `k >= 1`. The first time node `n - 1` pops off the heap on any run value, that distance is the answer. ## Worked example `n = 3`, `edges = [[0,1,1],[1,2,1],[0,2,3]]`, `labels = "aab"`, `k = 1`. Pop `(0, run 1)` at `d = 0`. Edge `0->1`: `labels[1] == 'a' == labels[0]`, so the new run is 2, which exceeds `k = 1` — dropped. Edge `0->2`: `labels[2] == 'b'`, run resets to 1, push `(2, 1)` at 3. Next pop is `(2, 1)` at 3, node 2 is `n - 1`, return 3. Raise `k` to 2 and the first edge survives: `(1, 2)` at cost 1, then `1->2` flips `'a'` to `'b'` and resets the run, giving `(2, 1)` at cost 2. That pops before the direct weight-3 edge, so the answer drops to 2. ## Complexity - **Time** O(k(V + E) log(kV)) — every one of the `n*k` states can enter the heap once, and each pop scans only the real out-edges of its node. - **Space** O(n*k) — one distance per `(node, run)` pair, plus the heap on top of it. ## Code (C++) ```cpp class Solution { public: int shortestPath(int n, vector>& edges, string labels, int k) { vector>> g(n); for (auto& e : edges) g[e[0]].push_back({e[1], e[2]}); const long long INF = LLONG_MAX / 4; // state = v * k + (run - 1), where run = consecutive identical labels ending at v vector dist((size_t)n * k, INF); priority_queue, vector>, greater<>> pq; dist[0] = 0; // node 0 with run = 1; k >= 1, so this is always legal pq.push({0LL, 0}); while (!pq.empty()) { auto [d, s] = pq.top(); pq.pop(); if (d > dist[s]) continue; int v = s / k, run = s % k + 1; if (v == n - 1) return (int)d; for (auto& [u, w] : g[v]) { int nrun = (labels[u] == labels[v]) ? run + 1 : 1; if (nrun > k) continue; int ns = u * k + nrun - 1; if (d + w < dist[ns]) { dist[ns] = d + w; pq.push({dist[ns], ns}); } } } return -1; } }; ``` ## One note The trap here is the sentinel, not the algorithm. A path through the state graph can touch `n*k` = 2.5 million states at `w <= 10^4` apiece, so the arithmetic bound is around `2.5*10^10` — well past `int`. I kept `dist` as `long long` and narrowed only at the `return`. The real answer fits in `int`, but `d + w` is evaluated against `dist[ns]` while `dist[ns]` is still the sentinel, and that is precisely where `INT_MAX` or `LLONG_MAX` as INF overflows into a negative number and silently turns into a shorter-looking path. `LLONG_MAX / 4` leaves headroom for the addition, which is the whole reason for the `/ 4`. The other detail worth keeping: test `v == n - 1` on the pop, never on the push. The first time you push the target you have some path to it, not the cheapest one; the pop carries Dijkstra's invariant, and returning there also spares you the remaining million states. Transferable: when a path constraint has bounded memory, widen the state rather than filter the edges. A suspiciously small bound like `1 <= k <= 50` sitting next to `n` at `5*10^4` is an invitation to multiply your node count by 50 and move on.