October 30Medium

Shortest path with at most k consecutive identical characters

String
Graph Theory
Heap
Shortest Path

Problem

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.

Solution

class Solution:
    def shortestPath(self, n: int, edges: List[List[int]], labels: str, k: int) -> int:
        graph = [{} for _ in range(n)]

        for u, v, w in edges:
            graph[u][v] = min(graph[u].get(v, w), w)

        pq = [(0, 1, 0)]
        heapify(pq)
        visited = {}
        while pq:
            weight, l, node = heappop(pq)
            if node in visited and visited[node] <= l:
                continue
            visited[node] = l
            if node == n - 1:
                return weight
            for u, w in graph[node].items():
                new_l = l + 1 if labels[u] == labels[node] else 1
                if new_l <= k and visited.get(u, 0) < new_l:
                    heappush(pq, (weight + w, new_l, u))
        return -1