3970. Shortest Path With At Most K Consecutive Identical Characters

LeetCode 原题

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.

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

思路: Dijkstra算法

我有一篇专门的文章讲这个算法，这道题也在其中，在此不再赘述

python

class Solution:
    def shortestPath(self, n: int, edges: List[List[int]], labels: str, k: int) -> int:
        graph = [[] for _ in range(n)]
        for start, end, weight in edges:
            graph[start].append((end, weight))
        dist = [[float('inf')]*(k+1) for _ in range(n)]
        dist[0][1] = 0
        heap = [] # weight, index, count
        heapq.heappush(heap, (0, 0, 1))
        while heap:
            total_weight, index, count = heapq.heappop(heap)
            if total_weight > dist[index][count]:
                continue
            if index == n-1:
                return total_weight
            for next_index, weight in graph[index]:
                next_count = count + 1 if labels[next_index] == labels[index] else 1
                if next_count > k:
                    continue
                if total_weight + weight < dist[next_index][next_count]:
                    dist[next_index][next_count] = total_weight + weight
                    heapq.heappush(heap, (total_weight + weight, next_index, next_count))
        return -1