Shortest Path With At Most K Consecutive Identical Characters solution and explanation

class Solution:
    def shortestPath(self, n: int, edges: List[List[int]], labels: str, k: int) -> int:
        g = [[] for _ in range(n)]
        for u, v, w in edges:
            g[u].append((v, w))

        dist = [[inf] * (k + 1) for _ in range(n)]
        dist[0][1] = 0
        pq = [(0, 0, 1)]
        while pq:
            d, u, cur = heappop(pq)
            if u == n - 1:
                return d
            if d > dist[u][cur]:
                continue
            for v, w in g[u]:
                nxt = 1 if labels[v] != labels[u] else cur + 1
                nd = d + w
                if nxt <= k and nd < dist[v][nxt]:
                    dist[v][nxt] = nd
                    heappush(pq, (nd, v, nxt))
        return -1

class Solution {
    public int shortestPath(int n, int[][] edges, String labels, int k) {
        List<int[]>[] g = new List[n];
        Arrays.setAll(g, i -> new ArrayList<>());
        for (int[] e : edges) {
            g[e[0]].add(new int[] {e[1], e[2]});
        }

        int[][] dist = new int[n][k + 1];
        for (int[] d : dist) {
            Arrays.fill(d, Integer.MAX_VALUE);
        }
        dist[0][1] = 0;

        PriorityQueue<int[]> pq = new PriorityQueue<>((a, b) -> Integer.compare(a[0], b[0]));
        pq.offer(new int[] {0, 0, 1});

        while (!pq.isEmpty()) {
            int[] p = pq.poll();
            int d = p[0], u = p[1], cur = p[2];
            if (u == n - 1) {
                return d;
            }
            if (d > dist[u][cur]) {
                continue;
            }
            for (int[] e : g[u]) {
                int v = e[0], w = e[1];
                int nxt = labels.charAt(v) != labels.charAt(u) ? 1 : cur + 1;
                int nd = d + w;
                if (nxt <= k && nd < dist[v][nxt]) {
                    dist[v][nxt] = nd;
                    pq.offer(new int[] {nd, v, nxt});
                }
            }
        }
        return -1;
    }
}

class Solution {
public:
    int shortestPath(int n, vector<vector<int>>& edges, string labels, int k) {
        vector<vector<pair<int, int>>> g(n);
        for (auto& e : edges) {
            g[e[0]].emplace_back(e[1], e[2]);
        }

        vector<vector<int>> dist(n, vector<int>(k + 1, INT_MAX));
        dist[0][1] = 0;

        priority_queue<tuple<int, int, int>, vector<tuple<int, int, int>>, greater<>> pq;
        pq.emplace(0, 0, 1);

        while (!pq.empty()) {
            auto [d, u, cur] = pq.top();
            pq.pop();
            if (u == n - 1) {
                return d;
            }
            if (d > dist[u][cur]) {
                continue;
            }
            for (auto [v, w] : g[u]) {
                int nxt = labels[v] != labels[u] ? 1 : cur + 1;
                int nd = d + w;
                if (nxt <= k && nd < dist[v][nxt]) {
                    dist[v][nxt] = nd;
                    pq.emplace(nd, v, nxt);
                }
            }
        }
        return -1;
    }
};

function shortestPath(n: number, edges: number[][], labels: string, k: number): number {
    const g: [number, number][][] = Array.from({ length: n }, () => []);
    for (const [u, v, w] of edges) {
        g[u].push([v, w]);
    }

    const dist = Array.from({ length: n }, () => new Array(k + 1).fill(Infinity));
    dist[0][1] = 0;

    const pq = new PriorityQueue<number[]>((a, b) => a[0] - b[0]);
    pq.enqueue([0, 0, 1]);

    while (!pq.isEmpty()) {
        const [d, u, cur] = pq.dequeue();

        if (u === n - 1) {
            return d;
        }
        if (d > dist[u][cur]) {
            continue;
        }

        for (const [v, w] of g[u]) {
            const nxt = labels[v] !== labels[u] ? 1 : cur + 1;
            const nd = d + w;
            if (nxt <= k && nd < dist[v][nxt]) {
                dist[v][nxt] = nd;
                pq.enqueue([nd, v, nxt]);
            }
        }
    }
    return -1;
}

func shortestPath(n int, edges [][]int, labels string, k int) int {
	g := make([][][2]int, n)
	for _, e := range edges {
		g[e[0]] = append(g[e[0]], [2]int{e[1], e[2]})
	}

	const inf = int(^uint(0) >> 1)
	dist := make([][]int, n)
	for i := range dist {
		dist[i] = make([]int, k+1)
		for j := range dist[i] {
			dist[i][j] = inf
		}
	}

	dist[0][1] = 0
	pq := &hp{{0, 0, 1}}
	heap.Init(pq)

	for pq.Len() > 0 {
		p := heap.Pop(pq).(tuple)
		d, u, cur := p.d, p.u, p.cur

		if u == n-1 {
			return d
		}
		if d > dist[u][cur] {
			continue
		}

		for _, e := range g[u] {
			v, w := e[0], e[1]
			nxt := cur + 1
			if labels[v] != labels[u] {
				nxt = 1
			}
			nd := d + w
			if nxt <= k && nd < dist[v][nxt] {
				dist[v][nxt] = nd
				heap.Push(pq, tuple{nd, v, nxt})
			}
		}
	}
	return -1
}

type tuple struct {
	d, u, cur int
}

type hp []tuple

func (h hp) Len() int           { return len(h) }
func (h hp) Less(i, j int) bool { return h[i].d < h[j].d }
func (h hp) Swap(i, j int)      { h[i], h[j] = h[j], h[i] }
func (h *hp) Push(v any)        { *h = append(*h, v.(tuple)) }
func (h *hp) Pop() any {
	a := *h
	v := a[len(a)-1]
	*h = a[:len(a)-1]
	return v
}