电动车游城市

/*
 * 思路：
 * 1. 使用Dijkstra算法求解最短路径问题。
 * 2. 在每个节点计算充电时间和行驶时间的总和。
 * 3. 优化路径以确保总时间最少。
 */
import java.util.*;
import java.util.stream.Collectors;

public class Solution {
    static class Node {
        int city, dist, chargeTime;
        Node(int city, int dist, int chargeTime) {
            this.city = city;
            this.dist = dist;
            this.chargeTime = chargeTime;
        }
    }

    public int minTime(int[][] paths, int cnt, int start, int end, int[] charge) {
        int n = charge.length;
        List<List<int[]>> graph = Arrays.stream(new List[n]).map(ArrayList::new).collect(Collectors.toList());
        Arrays.stream(paths).forEach(path -> {
            graph.get(path[0]).add(new int[]{path[1], path[2]});
            graph.get(path[1]).add(new int[]{path[0], path[2]});
        });

        PriorityQueue<Node> pq = new PriorityQueue<>(Comparator.comparingInt(a -> a.dist + a.chargeTime));
        pq.add(new Node(start, 0, 0));
        int[][] minTime = new int[n][cnt + 1];
        Arrays.stream(minTime).forEach(row -> Arrays.fill(row, Integer.MAX_VALUE));
        minTime[start][0] = 0;

        while (!pq.isEmpty()) {
            Node node = pq.poll();
            int city = node.city, dist = node.dist, chargeTime = node.chargeTime;
            if (city == end) return dist + chargeTime;
            graph.get(city).forEach(neighbor -> {
                int nextCity = neighbor[0], travelDist = neighbor[1];
                for (int newCharge = 0; newCharge + travelDist <= cnt; newCharge++) {
                    int totalChargeTime = newCharge * charge[city];
                    int totalTime = dist + travelDist + chargeTime + totalChargeTime;
                    if (totalTime < minTime[nextCity][newCharge + travelDist]) {
                        minTime[nextCity][newCharge + travelDist] = totalTime;
                        pq.add(new Node(nextCity, dist + travelDist, chargeTime + totalChargeTime));
                    }
                }
            });
        }

        return -1;
    }
}