电动车游城市

这个题解使用了带有优先队列（最小堆）的Dijkstra算法变种，结合状态转移来解决问题。每个状态由当前城市和车上的电量决定，形成一个状态空间。dist数组存储到达每个状态的最小时间。从起点开始，不断探索出发到其他城市的可能性，同时考虑在当前城市充电的可能性。当从优先队列中取出的状态的时间大于已记录的最小时间，则跳过该状态。算法结束的条件是当访问到终点城市时，队列中的第一个合法状态即为最小时间。此外，算法还考虑了每次充电的时间成本，并在每个城市尝试充电后再行驶到下一个城市，以及直接从当前电量出发到能达到的下一个城市。

时间复杂度: O(n^2 * cnt * log(n*cnt))

空间复杂度: O(n * cnt)

class Solution:
    def electricCarPlan(self, paths: List[List[int]], cnt: int, start: int, end: int, charge: List[int]) -> int:
        n = len(charge)
        dist = [[inf] * (cnt+1) for _ in range(n)]

        dist[start][0] = 0
        
        adj = defaultdict(list)
        for u,v,w in paths:
            adj[u].append((v,w))
            adj[v].append((u,w))
        q = []
        heappush(q, (0, start, 0))
        while q:
            t, u, c = heappop(q)
            if t > dist[u][c]:
                continue
            if u==end:
                return t
            
            if c<cnt:
                nt = t + charge[u]
                if nt < dist[u][c+1]:
                    dist[u][c+1] = nt
                    heappush(q, (nt, u, c+1))
            for v, w in adj[u]:
                if c >= w and t+w < dist[v][c-w]:
                    dist[v][c-w] = t + w
                    heappush(q, (t+w, v, c-w))