单源最短路径【学习算法】

import java.util.*;

/**
 * 在这个代码模板中，我们通过遍历int[] paths来构建图的邻接表。
 * 每个元素paths[i]表示从顶点paths[i][0]到顶点paths[i][1]的距离为paths[i][2]。
 *
 * 我们使用一个ArrayList来表示图的邻接表，每个顶点都有一个对应的列表，其中存储了与该顶点相连的边的目标顶点及其权重。
 *
 * 然后，我们可以使用Dijkstra算法来计算从给定起始顶点到其他顶点的最短距离。
 * 算法的时间复杂度为O((V+E)logV)，其中V为顶点的数量，E为边的数量。
 *
 * 这个代码模板使用了优先队列来实现最小堆，以提高算法的效率。算法的时间复杂度为O(ElogV)，其中E为边的数量，V为顶点的数量。
 */
public class Dijkstra {
    public static void main(String[] args) {
        //
        int[][] paths = {{0, 1, 2}, {0, 2, 4}, {1, 2, 1}, {1, 3, 4}, {1, 4, 2}, {2, 4, 3}, {3, 5, 2}, {4, 3, 3}, {4, 5, 2}};
        int n = 6;

        int[] dist = dijkstra(paths, n, 0);
        System.out.println(Arrays.toString(dist));

        int distD = dijkstraD(paths, n, 0,n-1);
        System.out.println(distD);
    }

    public static int[] dijkstra(int[][] paths, int n, int start) {
        //邻接表
        List[] graph = new ArrayList[n];
        //初始化
        for (int i = 0; i ();
        }
        //初始化
        for (int[] path : paths) {
            int source = path[0];
            int destination = path[1];
            int weight = path[2];
            graph[source].add(new int[]{destination, weight});
            graph[destination].add(new int[]{source, weight});
        }

        //距离
        int[] dist = new int[n];
        Arrays.fill(dist, Integer.MAX_VALUE);
        dist[start] = 0;

        //优先队列
        PriorityQueue pq = new PriorityQueue((a, b) -> a[1] - b[1]);
        //表示到达顶点 最小距离
        pq.offer(new int[]{start, 0});

        while (!pq.isEmpty()) {
            //取出
            int[] curr = pq.poll();
            int vertex = curr[0];
            int distance = curr[1];
            //跳过
            if (distance > dist[vertex]) {
                continue;
            }
            //更新
            for (int[] edge : graph[服务器托管网vertex]) {
                int newDistance = distance + edge[1];
                if (newDistance [] graph = new ArrayList[n];
        //初始化
        for (int i = 0; i ();
        }
        //初始化
        for (int[] path : paths) {
            int source = path[0];
            int destination = path[1];
            int weight = path[2];
            graph[source].add(new int[]{destination, weight});
            graph[destination].add(new int[]{source, weight});
        }

        //距离
        int[] dist = new int[n];
        Arrays.fill(dist, Integer.MAX_VALUE);
        dist[start] = 0;

        //优先队列
        PriorityQueue pq = new PriorityQueue((a, b) -> a[1] - b[1]);
        //表示到达顶点 最小距离
        pq.offer(new int[]{start, 0});

        while (!pq.isEmpty()) {
            int[] curr = pq.poll();
            int vertex = curr[0];
            int distance = curr[1];

            if (distance > dist[vertex]) {
                continue;
            }

            if (vertex==end){
                return distance;
            }

            for (int[] edge : graph[vertex]) {
                int newDistance = distance + edge[1];
                if (newDistance 

[0, 2, 3, 6, 4, 6]
6

class Solution {

    /*
        带限制的最短路径操作
        其实就是最短路径算法的变化版本，这里带限制的条件使得我们在向对应的队列加入元素的时候需要进行一定的判断，
        只有能够帮助我们的答案达到更优的操作才能够加入到队列当中，否则就会由于加入过多的元素导致最终超时。

        作者：豆小科
        链接：https://leetcode.cn/problems/minimum-cost-to-reach-destination-in-time/solutions/2224593/dai-xian-zhi-de-zui-duan-lu-jing-cao-zuo-d7t6/
        来源：力扣（LeetCode）
        著作权归作者所有。商业转载请联系作者获得授权，非商业转载请注明出处。
     */

   public static int minCost(int maxTime, int[][] edges, int[] passingFees) {
        // 使用最短路径进行处理
        int n = passingFees.length;
        //构造图邻接表
        List> graph = new ArrayList();
        for (int i = 0; i ());
        for (int[] edge : edges) {
            int x = edge[0];
            int y = edge[1];
            int time = edge[2];
            graph.get(x).add(new int[]{y, time});
            graph.get(y).add(new int[]{x, time});
        }
        //优先队列
        PriorityQueue queue = new PriorityQueue(Comparator.comparingInt(a -> a[1]));
        //时间 花费 当前结点
        queue.add(new int[]{0, passingFees[0], 0});
        //到达node的最少时间
        Map timeMap = new HashMap();

        while (!queue.isEmpty()) {
            int[] poll = queue.poll();
            int time = poll[0];
            int ct = poll[1];
            int node = poll[2];
            //继续
            if (time > maxTime) continue;
            //结束
            if (node == n - 1) return ct;

            //更新
            if (!timeMap.containsKey(node) || timeMap.get(node) > time) {
                timeMap.put(node, time);
                for (int[] e : graph.get(node)) {
                    queue.add(new int[]{e[1] + time, passingFees[e[0]] + ct, e[0]});
                }
            }
        }

        return -1;
    }
}

/**
     * 首先建图， 存储每个城市相邻的城市和距离
     *
     * 使用一个二维数组保存结果arr[i][j] = k， i = 所在城市， j = 剩余电量， k = 最短时间
     *
     * 用队列来记录每个路径的信息 {time,cur,power}， time = 已用时间， cur = 所在城市， power = 剩余电量 (使用优先队列来保证每次优先执行已用时间最少的路径)
     *
     * 每次只会有两种操作
     *
     * 充一次电 - 新时间 = 已用时间 + 当前城市每单位充电需要时间， 新电量 = 剩余电量 + 1
     * 去往下一个城市 - 新时间 = 已用时间 + 去往该需要消耗的时间， 新电量 = 剩余电量 − 去往该城市需要消耗的电量
     *
     * 作者：Fei服务器托管网lulue 
     * 链接：https://leetcode.cn/problems/DFPeFJ/solutions/974051/java-dijkstra-by-feilue-8p14/
     * 来源：力扣（LeetCode）
     * 著作权归作者所有。商业转载请联系作者获得授权，非商业转载请注明出处。
     */
class Solution {
        public int electricCarPlan(int[][] paths, int cnt, int start, int end, int[] charge) {
            int n = charge.length;

            //构造了图
            List[] map = new List[n];
            for(int i = 0; i  queue = new PriorityQueue((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;

                //充一次电
                //新时间 = 已用时间 + 当前城市每单位充电需要时间， 新电量 = 剩余电量 + 1
                if(power = 0 && t