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 weight wi = 3.
The corresponding concatenation of labels is "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 weight wi = 1.
  • Use edges[1] = [1, 2, 1] to reach node 2 with weight wi = 1.
The corresponding concatenation of labels is "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 * 104
  • 0 <= edges.length <= 5 * 104
  • edges[i] == [ui, vi, wi]
  • 0 <= ui, vi <= n - 1
  • ui != vi
  • 1 <= wi <= 104
  • labels consists of lowercase English letters
  • 1 <= 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;
    }
    
    

All Problems

All Solutions