3970. Shortest Path With At Most K Consecutive Identical Characters

You are given an integer n representing the number of nodes in a directed weighted graph, numbered from 0 to n - 1. This is represented by a 2D integer array edges, where edges[i] = [u_i, v_i, w_i] represents a directed edge from node u_i to node v_i with weight w_i.

You are also given a string labels of length n, where labels[i] is the character assigned to node i, and an integer k.

Return the minimum total edge weight of a path from node 0 to node n - 1 such that the concatenation of the labels of the nodes along the path contains at most k consecutive identical characters. If no valid path exists, return -1.

int dp[50505][55];
class Solution {
public:
    int shortestPath(int n, vector<vector<int>>& edges, string labels, int k) {
        memset(dp,-1,sizeof dp);
        vector<vector<pair<int,int>>> adj(n);
        for(auto& e : edges) {
            int u = e[0], v = e[1], w = e[2];
            adj[u].push_back({v,w});
        }
        priority_queue<array<int,3>,vector<array<int,3>>, greater<>> q;
        auto push = [&](int u, int w, int t) {
            if(t == k) return;
            if(dp[u][t] != -1 and dp[u][t] <= w) return;
            dp[u][t] = w;
            q.push({w,u,t});
        };
        push(0,0,0);
        while(q.size()) {
            auto [w,u,t] = q.top(); q.pop();
            if(dp[u][t] != w) continue;
            for(auto& [v,c] : adj[u]) {
                push(v,w+c, labels[u] == labels[v] ? t + 1 : 0);
            }
        }
        int res = INT_MAX;
        for(int i = 0; i < k; i++) if(dp[n-1][i] != -1) res = min(res, dp[n-1][i]);
        return res == INT_MAX ? -1 : res;
    }
};