3970. Shortest Path With At Most K Consecutive Identical Characters

/**
 * Problem: LeetCode 3970 - Shortest Path With At Most K Consecutive Identical Characters
 * Difficulty: Medium
 * Language: Java
 * Author: CodeByTushu
 */
import java.util.*;

/**
 * Problem: LeetCode 3970 - Shortest Path With At Most K Consecutive Identical Characters
 * Difficulty: Medium
 * Language: Java
 * Author: CodeByTushu
 */
class Solution {
    public int shortestPath(int n, int[][] edges, String labels, int k) {
        // adjacency list (arrays)
        int m = edges.length;
        int[] head = new int[n], nxt = new int[m], to = new int[m], wt = new int[m];
        Arrays.fill(head, -1);
        for (int i = 0; i < m; i++) {
            int u = edges[i][0];
            to[i] = edges[i][1];
            wt[i] = edges[i][2];
            nxt[i] = head[u];
            head[u] = i;
        }

        char[] lab = labels.toCharArray();
        int INF = Integer.MAX_VALUE;

        // dist[u * (k + 1) + r], r in [1..k]
        int[] dist = new int[n * (k + 1)];
        Arrays.fill(dist, INF);

        // heap entry: (distance << 32) | stateIndex
        PriorityQueue<Long> pq = new PriorityQueue<>();
        int startState = 0 * (k + 1) + 1;
        dist[startState] = 0;
        pq.offer((long) 0 << 32 | startState);

        while (!pq.isEmpty()) {
            long top = pq.poll();
            int d = (int) (top >>> 32);
            int state = (int) (top & 0xFFFFFFFFL);

            if (d > dist[state]) continue;

            int u = state / (k + 1);
            int r = state % (k + 1);

            if (u == n - 1) return d; // first time we pop n-1 is the minimum

            for (int e = head[u]; e != -1; e = nxt[e]) {
                int v = to[e];
                int nr;
                if (lab[v] == lab[u]) {
                    nr = r + 1;
                    if (nr > k) continue;
                } else {
                    nr = 1;
                }

                int nd = d + wt[e];
                int ns = v * (k + 1) + nr;
                if (nd < dist[ns]) {
                    dist[ns] = nd;
                    pq.offer(((long) nd << 32) | ns);
                }
            }
        }

        return -1;
    }
}

"""
Problem: LeetCode 3970 - Shortest Path With At Most K Consecutive Identical Characters
Difficulty: Medium
Language: Python
Author: CodeByTushu
"""
import heapq
from typing import List

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

        INF = float('inf')
        dist = [INF] * (n * (k + 1))

        start_state = 0 * (k + 1) + 1
        dist[start_state] = 0
        pq = [(0, start_state)]

        while pq:
            d, state = heapq.heappop(pq)
            if d > dist[state]:
                continue

            u = state // (k + 1)
            r = state % (k + 1)

            if u == n - 1:
                return d

            for v, w in adj[u]:
                if labels[v] == labels[u]:
                    nr = r + 1
                    if nr > k:
                        continue
                else:
                    nr = 1

                nd = d + w
                ns = v * (k + 1) + nr
                if nd < dist[ns]:
                    dist[ns] = nd
                    heapq.heappush(pq, (nd, ns))

        return -1

/**
 * Problem: LeetCode 3970 - Shortest Path With At Most K Consecutive Identical Characters
 * Difficulty: Medium
 * Language: C++
 * Author: CodeByTushu
 */
#include <vector>
#include <queue>
#include <string>
#include <cstdint>

using namespace std;

class Solution {
public:
    int shortestPath(int n, vector<vector<int>>& edges, string labels, int k) {
        int m = edges.size();
        vector<int> head(n, -1), nxt(m), to(m), wt(m);
        for (int i = 0; i < m; i++) {
            int u = edges[i][0];
            to[i] = edges[i][1];
            wt[i] = edges[i][2];
            nxt[i] = head[u];
            head[u] = i;
        }

        const int INF = 1e9;
        vector<int> dist(n * (k + 1), INF);

        priority_queue<uint64_t, vector<uint64_t>, greater<uint64_t>> pq;
        int startState = 0 * (k + 1) + 1;
        dist[startState] = 0;
        pq.push(((uint64_t)0 << 32) | startState);

        while (!pq.empty()) {
            uint64_t top = pq.top();
            pq.pop();

            int d = (int)(top >> 32);
            int state = (int)(top & 0xFFFFFFFFULL);

            if (d > dist[state]) continue;

            int u = state / (k + 1);
            int r = state % (k + 1);

            if (u == n - 1) return d;

            for (int e = head[u]; e != -1; e = nxt[e]) {
                int v = to[e];
                int nr = (labels[v] == labels[u]) ? (r + 1) : 1;
                if (nr > k) continue;

                int nd = d + wt[e];
                int ns = v * (k + 1) + nr;
                if (nd < dist[ns]) {
                    dist[ns] = nd;
                    pq.push(((uint64_t)nd << 32) | ns);
                }
            }
        }

        return -1;
    }
};

/**
 * Problem: LeetCode 3970 - Shortest Path With At Most K Consecutive Identical Characters
 * Difficulty: Medium
 * Language: JavaScript
 * Author: CodeByTushu
 */
/**
 * @param {number} n
 * @param {number[][]} edges
 * @param {string} labels
 * @param {number} k
 * @return {number}
 */
var shortestPath = function(n, edges, labels, k) {
    const m = edges.length;
    const head = new Int32Array(n).fill(-1);
    const nxt = new Int32Array(m), to = new Int32Array(m), wt = new Int32Array(m);

    for (let i = 0; i < m; i++) {
        const u = edges[i][0];
        to[i] = edges[i][1]; wt[i] = edges[i][2];
        nxt[i] = head[u]; head[u] = i;
    }

    const INF = 2147483647;
    const dist = new Int32Array(n * (k + 1)).fill(INF);

    class MinHeap {
        constructor() { this.d = []; this.s = []; }
        push(dv, sv) {
            this.d.push(dv); this.s.push(sv);
            let i = this.d.length - 1;
            while (i > 0) {
                const p = (i - 1) >> 1;
                if (this.d[i] < this.d[p]) { this._swap(i, p); i = p; } else break;
            }
        }
        pop() {
            const topD = this.d[0], topS = this.s[0];
            const lastD = this.d.pop(), lastS = this.s.pop();
            if (this.d.length > 0) {
                this.d[0] = lastD; this.s[0] = lastS;
                let i = 0, len = this.d.length;
                while ((i << 1) + 1 < len) {
                    let l = (i << 1) + 1, r = l + 1, best = i;
                    if (this.d[l] < this.d[best]) best = l;
                    if (r < len && this.d[r] < this.d[best]) best = r;
                    if (best !== i) { this._swap(i, best); i = best; } else break;
                }
            }
            return [topD, topS];
        }
        size() { return this.d.length; }
        _swap(i, j) {
            const td = this.d[i]; this.d[i] = this.d[j]; this.d[j] = td;
            const ts = this.s[i]; this.s[i] = this.s[j]; this.s[j] = ts;
        }
    }

    const pq = new MinHeap();
    const startState = 0 * (k + 1) + 1;
    dist[startState] = 0;
    pq.push(0, startState);

    while (pq.size() > 0) {
        const [d, state] = pq.pop();
        if (d > dist[state]) continue;

        const u = Math.floor(state / (k + 1));
        const r = state % (k + 1);

        if (u === n - 1) return d;

        for (let e = head[u]; e != -1; e = nxt[e]) {
            const v = to[e];
            const nr = (labels.charCodeAt(v) === labels.charCodeAt(u)) ? (r + 1) : 1;
            if (nr > k) continue;

            const nd = d + wt[e];
            const ns = v * (k + 1) + nr;
            if (nd < dist[ns]) {
                dist[ns] = nd;
                pq.push(nd, ns);
            }
        }
    }

    return -1;
};