抄代码也很辛苦啊 第一次实现最短路径算法

给你一个由 n 个节点（下标从 0 开始）组成的无向加权图，该图由一个描述边的列表组成，其中 edges[i] = [a, b]
表示连接节点 a 和 b 的一条无向边，且该边遍历成功的概率为 succProb[i] 。

指定两个节点分别作为起点 start 和终点 end ，请你找出从起点到终点成功概率最大的路径，并返回其成功概率。

如果不存在从 start 到 end 的路径，请 返回 0 。只要答案与标准答案的误差不超过 1e-5 ，就会被视作正确答案。

来源：力扣（LeetCode）
链接：https://leetcode-cn.com/problems/path-with-maximum-probability
著作权归领扣网络所有。商业转载请联系官方授权，非商业转载请注明出处。

例子不粘了，大眼一扫就知道应该实现个最短路径算法，也知道去算法导论的哪去抄，但是实现起来干了我两个多小时
种植把代码粘过来，留个纪念吧

class Solution {
    //妈的还有时间要求 没办法了
    class pq {
        double[] poss;
        int[] nodes;//当前位置存的哪个节点
        int[] index;//第i个节点在poss和nodes中的哪个位置
        int n;//总共里面有n个节点
        pq(int N, int start) {
            n = N;
            poss = new double[n];
            nodes = new int[n];
            index = new int[n];

            for(int i = 0; i < n; ++i) {
                index[i] = i;
                nodes[i] = i;
            }

            increase(start, 1);
        }

        void swap(int node1, int node2) {
            //交换两个节点 所有东西都交换
            int i1 = index[node1], i2 = index[node2];
            index[node1] = i2;
            index[node2] = i1;
            double td = poss[i1];
            poss[i1] = poss[i2];
            poss[i2] = td;
            nodes[i1] = node2;
            nodes[i2] = node1;
        }

        void increase(int node, double p) {
            //将node的value变成p node可能会往前走
            int i = index[node];
            poss[i] = p;
            while(i != 0 && poss[i] > poss[(i - 1) / 2] ) {
                swap(nodes[i], nodes[(i - 1) / 2]);
                i = (i - 1) / 2;
            }
        }

        double getPoss() {
            //返回队首概率
            return poss[0];
        }

        int getNode() {
            //返回队首节点好
            return nodes[0];
        }

        void removeFirst() {
            //其实这个是需要decrease的？
            swap(nodes[0], nodes[n - 1]);
            --n;
            int i = 0;
            while(i < n) {
                //和它的两孩子中最大的换
                double max = poss[i];
                int maxIndex = i;
                if(i * 2 + 1 < n && poss[i * 2 + 1] > max) {
                    max = poss[i * 2 + 1];
                    maxIndex = i * 2 + 1;
                }
                if(i * 2 + 2 < n && poss[i * 2 + 2]  > max) {
                    max = poss[i * 2 + 2];
                    maxIndex = i * 2 + 2;
                }
                if(maxIndex != i) {
                    swap(nodes[maxIndex], nodes[i]);
                    i = maxIndex;
                } else {
                    i = n;
                }
            }
        }
    }


    public double maxProbability(int n, int[][] edges, double[] succProb, int start, int end) {
        //DJ特斯拉最短路径算法 先实现最简单的遍历找最小值的
        HashMap<Integer, List<Integer>> v = new HashMap<>();
        pq queue = new pq(n, start);
        double[] ret = new double[n];
        for(int i = 0; i < n; ++i) {
            v.put(i, new ArrayList<>());
        }
        ret[start] = 1.0;
        for(int i = 0; i < edges.length; ++i) {
            int[] edge = edges[i];
            v.get(edge[0]).add(i);
            v.get(edge[1]).add(i);//因为在访问某条边的时候还需要访问这条边的 poss 所以...
        }

        while(queue.getNode() != end && queue.getPoss() != 0) {
            int curNode = queue.getNode();
            List<Integer> edgeIndex = v.get(curNode);
            double curPoss = queue.getPoss();

            //对于每一条边 relax 一下
            for(Integer i : edgeIndex) {
                double edgeposs = succProb[i];
                int next = edges[i][0] == curNode ? edges[i][1] : edges[i][0];
                double prev = ret[next];
                if(prev < edgeposs * curPoss) {
                    queue.increase(next, edgeposs * curPoss);
                    ret[next] = edgeposs * curPoss;
                }
            }

            queue.removeFirst();
        }

        return ret[end];
    }
}

我滴妈呀，太刺激了