3970. Shortest Path With At Most K Consecutive Identical Characters
Problem Overview
Every edge weight is positive, so the cheapest route from node 0 to node n minus 1 is a Dijkstra search.
Intuition
Every edge weight is positive, so the cheapest route from node 0 to node n minus 1 is a Dijkstra search. The plain shortest path can walk through more than k identical labels in a row, while a dearer path stays legal by changing letters. Arriving at the same node with a longer current run leaves less room for another copy of that letter, so one distance per node is not enough. The state is the node together with the length of the run that ends there, and that length is at most k. The starting letter is already a run of 1. The next letter grows the run when it matches and resets the run to 1 when it differs. A run past k is discarded. Distances are kept in 64 bit integers so a long sum does not wrap while the heap is still running. The first time the destination leaves the heap, its distance is the answer.
Algorithm
- 1Link every directed edge from its source in one pass.
- 2Set the distance of node 0 with run length 1 to 0, and push that state.
- 3Pop the cheapest state. Skip it when a better distance to the same state was already recorded.
- 4Return that distance when the node is n minus 1.
- 5For each outgoing edge, set the next run to the old run plus 1 or to 1, and relax the neighbor when the run is still at most k.
- 6Return minus 1 when the heap empties first.
Example Walkthrough
Input: n = 3, edges = [[0,1,1],[1,2,1],[0,2,3]], labels = "aab"
- 1.With k = 1 the path 0, 1, 2 reads a, a, b. Two a letters in a row are too many, so that path is dropped.
- 2.The direct edge from 0 to 2 reads a, b and costs 3.
- 3.With k = 2 the path through node 1 is legal and costs 1 plus 1, which is 2.
Output: 3 when k is 1, and 2 when k is 2
Common Pitfalls
- •The starting node counts. Its label is a run of length 1, even though no edge has been used yet.
- •A smaller distance with a longer run is not always better. The shorter run may be the only one that can continue.
- •Adding edge weights in a 32 bit integer can wrap on a long path and look smaller than a real distance.
- •The first time the destination is popped is the answer. Later pops of the same node have a larger or equal cost.
// Approach: Edge weights are positive, so Dijkstra finds the cheapest path.
// Reaching a node with a longer run of the same letter leaves less room, so
// the state is the node plus the current run, which is at most k. The start
// letter is a run of 1. The next letter grows that run when it matches and
// resets it to 1 otherwise. Runs past k are dropped. Distances are 64-bit
// so a long path does not wrap during the search.
// Time: O((n + m) * k * log(n * k)) Space: O(n * k + m)
public class Solution
{
public int ShortestPath(int n, int[][] edges, string labels, int k)
{
int m = edges.Length;
int[] head = new int[n];
Array.Fill(head, -1);
int[] to = new int[m];
int[] weight = new int[m];
int[] next = new int[m];
for (int i = 0; i < m; i++)
{
int u = edges[i][0];
to[i] = edges[i][1];
weight[i] = edges[i][2];
next[i] = head[u];
head[u] = i;
}
int stride = k + 1;
long[] dist = new long[n * stride];
Array.Fill(dist, long.MaxValue);
dist[1] = 0;
var pq = new PriorityQueue<int, long>();
pq.Enqueue(1, 0);
while (pq.TryDequeue(out int state, out long d))
{
if (d != dist[state])
continue;
int u = state / stride;
if (u == n - 1)
return (int)d;
int cur = state - u * stride;
char here = labels[u];
for (int e = head[u]; e >= 0; e = next[e])
{
int v = to[e];
int run = labels[v] == here ? cur + 1 : 1;
if (run > k)
continue;
long nd = d + weight[e];
int ns = v * stride + run;
if (nd < dist[ns])
{
dist[ns] = nd;
pq.Enqueue(ns, nd);
}
}
}
return -1;
}
}