Shortest Path With At Most K Consecutive Identical Characters | Leetcode 3970

class Solution {
    struct Node {
        int u;
        int count;
        int wt;
        
        // Min-heap comparison based on weight
        bool operator>(const Node& other) const {
            return wt > other.wt;
        }
    };

public:
    int shortestPath(int n, vector<vector<int>>& edges, string labels, int k) {
        // Step 1: Make the Adjacency List
        vector<vector<pair<int, int>>> adj(n);
        for (const auto& edge : edges)
            adj[edge[0]].push_back({edge[1], edge[2]});
        
        // Step 2: Assign data structures
        // dist[node][consecutive_count] = min_weight
        // We use 1e9 as a safe equivalent for infinity to prevent overflow
        vector<vector<int>> dist(n, vector<int>(k + 1, 1e9)); 
        
        priority_queue<Node, vector<Node>, greater<Node>> minheap;
        
        // Start at node 0, with 1 consecutive character (labels[0]), weight 0
        dist[0][1] = 0;
        minheap.push({0, 1, 0});
        
        // Step 3: Apply Dijkstra with state (node, consecutive_count)
        while (!minheap.empty()) {
            auto [u, count, wt] = minheap.top();
            minheap.pop();
            
            // Found Destination
            if (u == n - 1)
                return wt;
            
            // Skip outdated states
            if (wt > dist[u][count])
                continue;
            
            // Process adjacent nodes
            for (const auto& [v, edge_wt] : adj[u]) {
                // Calculate new consecutive count
                int next_count = (labels[v] == labels[u]) ? count + 1 : 1;
                
                // If taking this edge violates the k-consecutive rule, skip it
                if (next_count > k)
                    continue;
                
                int next_wt = wt + edge_wt;
                
                // Relaxation step
                if (next_wt < dist[v][next_count]) {
                    dist[v][next_count] = next_wt;
                    minheap.push({v, next_count, next_wt});
                }
            }
        }
        return -1;
    }
};
/*
//JAVA
import java.util.*;

class Solution {

    static class Node {
        int u;
        int count;
        int wt;

        Node(int u, int count, int wt) {
            this.u = u;
            this.count = count;
            this.wt = wt;
        }
    }

    public int shortestPath(int n, int[][] edges, String labels, int k) {

        // Step 1: Build adjacency list
        List<int[]>[] adj = new ArrayList[n];
        for (int i = 0; i < n; i++) {
            adj[i] = new ArrayList<>();
        }

        for (int[] edge : edges) {
            adj[edge[0]].add(new int[]{edge[1], edge[2]});
        }

        // Step 2: dist[node][count] = minimum weight
        int INF = (int) 1e9;
        int[][] dist = new int[n][k + 1];
        for (int i = 0; i < n; i++) {
            Arrays.fill(dist[i], INF);
        }

        PriorityQueue<Node> pq = new PriorityQueue<>((a, b) -> a.wt - b.wt);

        dist[0][1] = 0;
        pq.offer(new Node(0, 1, 0));

        // Step 3: Dijkstra
        while (!pq.isEmpty()) {
            Node curr = pq.poll();

            int u = curr.u;
            int count = curr.count;
            int wt = curr.wt;

            if (u == n - 1) {
                return wt;
            }

            if (wt > dist[u][count]) {
                continue;
            }

            for (int[] edge : adj[u]) {
                int v = edge[0];
                int edgeWt = edge[1];

                int nextCount = (labels.charAt(v) == labels.charAt(u)) ? count + 1 : 1;

                if (nextCount > k) {
                    continue;
                }

                int nextWt = wt + edgeWt;

                if (nextWt < dist[v][nextCount]) {
                    dist[v][nextCount] = nextWt;
                    pq.offer(new Node(v, nextCount, nextWt));
                }
            }
        }

        return -1;
    }
}

#Python
import heapq
from typing import List

class Solution:
    def shortestPath(self, n: int, edges: List[List[int]], labels: str, k: int) -> int:

        # Step 1: Build adjacency list
        adj = [[] for _ in range(n)]
        for u, v, wt in edges:
            adj[u].append((v, wt))

        # Step 2: dist[node][count] = minimum weight
        INF = 10**9
        dist = [[INF] * (k + 1) for _ in range(n)]

        minheap = []

        dist[0][1] = 0
        heapq.heappush(minheap, (0, 0, 1))  # (weight, node, count)

        # Step 3: Dijkstra
        while minheap:
            wt, u, count = heapq.heappop(minheap)

            if u == n - 1:
                return wt

            if wt > dist[u][count]:
                continue

            for v, edge_wt in adj[u]:
                next_count = count + 1 if labels[v] == labels[u] else 1

                if next_count > k:
                    continue

                next_wt = wt + edge_wt

                if next_wt < dist[v][next_count]:
                    dist[v][next_count] = next_wt
                    heapq.heappush(minheap, (next_wt, v, next_count))

        return -1
*/