Path with Maximum Probability

class Solution {
public:
    double maxProbability(int n, vector<vector<int>>& edges, vector<double>& succProb,
                          int start_node, int end_node) {
        vector<vector<pair<int,double>>> adj(n);
        for (int i = 0; i < (int)edges.size(); ++i) {
            adj[edges[i][0]].push_back({edges[i][1], succProb[i]});
            adj[edges[i][1]].push_back({edges[i][0], succProb[i]});
        }
        vector<double> prob(n, 0.0);
        prob[start_node] = 1.0;
        priority_queue<pair<double,int>> pq;
        pq.push({1.0, start_node});
        while (!pq.empty()) {
            auto [p, u] = pq.top(); pq.pop();
            if (u == end_node) return p;
            if (p < prob[u]) continue;
            for (auto [v, w] : adj[u]) {
                double np = p * w;
                if (np > prob[v]) {
                    prob[v] = np;
                    pq.push({np, v});
                }
            }
        }
        return 0.0;
    }
};

type probItem struct {
    p float64
    u int
}
type probHeap []probItem

func (h probHeap) Len() int            { return len(h) }
func (h probHeap) Less(i, j int) bool  { return h[i].p > h[j].p } // max-heap on p
func (h probHeap) Swap(i, j int)       { h[i], h[j] = h[j], h[i] }
func (h *probHeap) Push(x interface{}) { *h = append(*h, x.(probItem)) }
func (h *probHeap) Pop() interface{} {
    old := *h
    n := len(old)
    v := old[n-1]
    *h = old[:n-1]
    return v
}

func maxProbability(n int, edges [][]int, succProb []float64, startNode int, endNode int) float64 {
    type nbr struct {
        v int
        w float64
    }
    adj := make([][]nbr, n)
    for i, e := range edges {
        adj[e[0]] = append(adj[e[0]], nbr{e[1], succProb[i]})
        adj[e[1]] = append(adj[e[1]], nbr{e[0], succProb[i]})
    }
    prob := make([]float64, n)
    prob[startNode] = 1.0
    pq := &probHeap{{1.0, startNode}}
    heap.Init(pq)
    for pq.Len() > 0 {
        it := heap.Pop(pq).(probItem)
        p, u := it.p, it.u
        if u == endNode {
            return p
        }
        if p < prob[u] {
            continue
        }
        for _, e := range adj[u] {
            np := p * e.w
            if np > prob[e.v] {
                prob[e.v] = np
                heap.Push(pq, probItem{np, e.v})
            }
        }
    }
    return 0.0
}

import heapq

class Solution:
    def maxProbability(self, n: int, edges: List[List[int]], succProb: List[float],
                       start_node: int, end_node: int) -> float:
        adj: List[List[tuple]] = [[] for _ in range(n)]
        for (a, b), p in zip(edges, succProb):
            adj[a].append((b, p))
            adj[b].append((a, p))
        prob = [0.0] * n
        prob[start_node] = 1.0
        # Max-heap via negation.
        pq = [(-1.0, start_node)]
        while pq:
            neg_p, u = heapq.heappop(pq)
            p = -neg_p
            if u == end_node:
                return p
            if p < prob[u]:
                continue
            for v, w in adj[u]:
                np = p * w
                if np > prob[v]:
                    prob[v] = np
                    heapq.heappush(pq, (-np, v))
        return 0.0

class MaxHeap {
    constructor() { this.h = []; }
    size() { return this.h.length; }
    push(x) {
        this.h.push(x);
        let i = this.h.length - 1;
        while (i > 0) {
            const p = (i - 1) >> 1;
            if (this.h[p][0] >= this.h[i][0]) break;
            [this.h[p], this.h[i]] = [this.h[i], this.h[p]];
            i = p;
        }
    }
    pop() {
        const top = this.h[0];
        const last = this.h.pop();
        if (this.h.length > 0) {
            this.h[0] = last;
            const n = this.h.length;
            let i = 0;
            while (true) {
                const l = 2 * i + 1, r = 2 * i + 2;
                let best = i;
                if (l < n && this.h[l][0] > this.h[best][0]) best = l;
                if (r < n && this.h[r][0] > this.h[best][0]) best = r;
                if (best === i) break;
                [this.h[best], this.h[i]] = [this.h[i], this.h[best]];
                i = best;
            }
        }
        return top;
    }
}

function maxProbability(n, edges, succProb, start_node, end_node) {
    const adj = Array.from({ length: n }, () => []);
    for (let i = 0; i < edges.length; i++) {
        adj[edges[i][0]].push([edges[i][1], succProb[i]]);
        adj[edges[i][1]].push([edges[i][0], succProb[i]]);
    }
    const prob = new Array(n).fill(0);
    prob[start_node] = 1;
    const pq = new MaxHeap();
    pq.push([1, start_node]);
    while (pq.size() > 0) {
        const [p, u] = pq.pop();
        if (u === end_node) return p;
        if (p < prob[u]) continue;
        for (const [v, w] of adj[u]) {
            const np = p * w;
            if (np > prob[v]) {
                prob[v] = np;
                pq.push([np, v]);
            }
        }
    }
    return 0;
}

class Solution {
    public double maxProbability(int n, int[][] edges, double[] succProb,
                                 int start_node, int end_node) {
        List<List<double[]>> adj = new ArrayList<>();
        for (int i = 0; i < n; i++) adj.add(new ArrayList<>());
        for (int i = 0; i < edges.length; i++) {
            adj.get(edges[i][0]).add(new double[]{edges[i][1], succProb[i]});
            adj.get(edges[i][1]).add(new double[]{edges[i][0], succProb[i]});
        }
        double[] prob = new double[n];
        prob[start_node] = 1.0;
        // Max-heap on probability.
        PriorityQueue<double[]> pq = new PriorityQueue<>((a, b) -> Double.compare(b[0], a[0]));
        pq.offer(new double[]{1.0, start_node});
        while (!pq.isEmpty()) {
            double[] cur = pq.poll();
            double p = cur[0];
            int u = (int) cur[1];
            if (u == end_node) return p;
            if (p < prob[u]) continue;
            for (double[] e : adj.get(u)) {
                int v = (int) e[0];
                double w = e[1];
                double np = p * w;
                if (np > prob[v]) {
                    prob[v] = np;
                    pq.offer(new double[]{np, v});
                }
            }
        }
        return 0.0;
    }
}

class MaxHeap {
    h: [number, number][];
    constructor() { this.h = []; }
    size(): number { return this.h.length; }
    push(x: [number, number]): void {
        this.h.push(x);
        let i = this.h.length - 1;
        while (i > 0) {
            const p = (i - 1) >> 1;
            if (this.h[p][0] >= this.h[i][0]) break;
            [this.h[p], this.h[i]] = [this.h[i], this.h[p]];
            i = p;
        }
    }
    pop(): [number, number] {
        const top = this.h[0];
        const last = this.h.pop()!;
        if (this.h.length > 0) {
            this.h[0] = last;
            const n = this.h.length;
            let i = 0;
            while (true) {
                const l = 2 * i + 1, r = 2 * i + 2;
                let best = i;
                if (l < n && this.h[l][0] > this.h[best][0]) best = l;
                if (r < n && this.h[r][0] > this.h[best][0]) best = r;
                if (best === i) break;
                [this.h[best], this.h[i]] = [this.h[i], this.h[best]];
                i = best;
            }
        }
        return top;
    }
}

function maxProbability(n: number, edges: number[][], succProb: number[], start_node: number, end_node: number): number {
    const adj: [number, number][][] = Array.from({ length: n }, () => []);
    for (let i = 0; i < edges.length; i++) {
        adj[edges[i][0]].push([edges[i][1], succProb[i]]);
        adj[edges[i][1]].push([edges[i][0], succProb[i]]);
    }
    const prob: number[] = new Array(n).fill(0);
    prob[start_node] = 1;
    const pq = new MaxHeap();
    pq.push([1, start_node]);
    while (pq.size() > 0) {
        const [p, u] = pq.pop();
        if (u === end_node) return p;
        if (p < prob[u]) continue;
        for (const [v, w] of adj[u]) {
            const np = p * w;
            if (np > prob[v]) {
                prob[v] = np;
                pq.push([np, v]);
            }
        }
    }
    return 0;
}