Welcome to Subscribe On Youtube
3970. Shortest Path With At Most K Consecutive Identical Characters
Description
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:
- Use
edges[2] = [0, 2, 3]to reach node 2 with a weightwi = 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:
- Use
edges[0] = [0, 1, 1]to reach node 1 with weightwi = 1. - Use
edges[1] = [1, 2, 1]to reach node 2 with weightwi = 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 <= 104labelsconsists of lowercase English letters1 <= k <= 50
Solutions
Solution 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; } }; -
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 -
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 } -
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; }