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] = [ui, vi, wi] represents a directed edge from node ui to node vi with weight wi.
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.
Example 1:
Input: n = 3, edges = [[0,1,1],[1,2,1],[0,2,3]], labels = "aab", k = 1
Output: 3
Explanation:
The optimal valid path from node 0 to node 2 is as follows:
edges[2] = [0, 2, 3] to reach node 2 with a weight wi = 3."ab", which satisfies at most k = 1 consecutive identical characters. Thus, the answer is 3.Example 2:
Input: n = 3, edges = [[0,1,1],[1,2,1],[0,2,3]], labels = "aab", k = 2
Output: 2
Explanation:
The optimal valid path from node 0 to node 2 is as follows:
edges[0] = [0, 1, 1] to reach node 1 with weight wi = 1.edges[1] = [1, 2, 1] to reach node 2 with weight wi = 1."aab", which satisfies at most k = 2 consecutive identical characters. Thus, the answer is 2.Example 3:
Input: n = 3, edges = [[0,1,1],[1,2,1]], labels = "aaa", k = 2
Output: -1
Explanation:
There is no valid path from node 0 to node 2 that satisfies at most k = 2 consecutive identical characters. Thus, the answer is -1.
Constraints:
1 <= n == labels.length <= 5 * 1040 <= edges.length <= 5 * 104edges[i] == [ui, vi, wi]0 <= ui, vi <= n - 1ui != vi1 <= wi <= 104labels consists of lowercase English letters1 <= k <= 50Loading editor...
3 [[0,1,1],[1,2,1],[0,2,3]] "aab" 1