python3 解法, 执行用时: 104 ms, 内存消耗: 17.2 MB, 提交时间: 2023-10-25 23:10:12

class Solution:
    def electricCarPlan(self, paths: List[List[int]], cnt: int, start: int, end: int, charge: List[int]) -> int:
        nxt = defaultdict(list)
        for u, v, w in paths:
            nxt[u].append((v, w))
            nxt[v].append((u, w))
        d, pq = {}, [(0, start, 0)]
        while pq:
            w, u, c = heappop(pq)
            if (u, c) in d:
                continue
            if (u, c) == (end, 0):
                return w
            d[(u, c)] = w
            for v, w2 in nxt[u]:
                if c>=w2 and (v, c-w2) not in d:
                    heappush(pq, (w+w2, v, c-w2))
            if c<cnt:
                heappush(pq, (w+charge[u], u, c+1))

java 解法, 执行用时: 15 ms, 内存消耗: 42.6 MB, 提交时间: 2023-10-25 23:09:35

class Solution {
    public int electricCarPlan(int[][] paths, int cnt, int start, int end, int[] charge) {
        int n = charge.length;
        
        List<int[]>[] map = new List[n];
        for(int i = 0; i < n; i++) map[i] = new ArrayList();
        for(int[] path : paths){
            map[path[0]].add(new int[]{path[1], path[2]});
            map[path[1]].add(new int[]{path[0], path[2]});
        }

        int[][] res = new int[n][cnt+1];
        for(int[] i : res) Arrays.fill(i, Integer.MAX_VALUE/2);
        res[start][0] = 0;

        Queue<int[]> queue = new PriorityQueue<int[]>((x, y) -> (x[0] - y[0]));
        queue.offer(new int[]{0, start, 0});
        
        while(!queue.isEmpty()){
            int[] arr = queue.poll();
            int time = arr[0];
            int cur = arr[1];
            int power = arr[2];

            if(time > res[cur][power]) continue;
            if(cur == end) return time;

            if(power < cnt){
                int t = time + charge[cur];
                if(t < res[cur][power+1]){
                    res[cur][power+1] = t;
                    queue.offer(new int[]{t, cur, power+1});
                }
            }

            for(int[] path : map[cur]){
                int next = path[0];
                int cost = path[1];
                int t = time + cost;
                int p = power - cost;
                if(p >= 0 && t < res[next][p]){
                    res[next][p] = t;
                    queue.offer(new int[]{t, next, p});
                }
            }

        }

        return -1;
    }
}

cpp 解法, 执行用时: 32 ms, 内存消耗: 12.9 MB, 提交时间: 2023-10-25 23:09:19

const int INF = 0x3f3f3f3f;

class Solution {
public:
    int electricCarPlan(vector<vector<int>>& paths, int cnt, int start, int end, vector<int>& charge) {
        int n = charge.size();
        vector<vector<int>> dist(n, vector<int>(cnt + 1, INF));
        dist[start][0] = 0;
        
        vector<vector<pair<int, int>>> adj(n);
        for (auto &path : paths) {
            int u = path[0], v = path[1], w = path[2];
            adj[u].emplace_back(v, w);
            adj[v].emplace_back(u, w);
        }
        priority_queue<tuple<int, int, int>, vector<tuple<int, int, int>>, greater<>> pq;
        pq.emplace(0, start, 0);
        
        while (!pq.empty()) {
            auto [t, u, c] = pq.top();
            pq.pop();
            if (t > dist[u][c])
                continue;
            if (u == end)
                return t;

            // 当前电不满，充电一分钟，状态变为(u,c+1)
            if (c < cnt) {
                int nt = t + charge[u];
                if (nt < dist[u][c + 1]) {
                    dist[u][c + 1] = nt;
                    pq.emplace(nt, u, c + 1);
                }
            }

            // 如果一条边(u,v,w)能走，尝试走这条边，状态变为(v,c-w)
            for (auto [v, w] : adj[u]) {
                if (c >= w && t + w < dist[v][c - w]) {
                    dist[v][c - w] = t + w;
                    pq.emplace(t + w, v, c - w);
                }
            }
        }
        
        return -1;
    }
};