dijkstra template

dijkstra.h

struct cmp
{
    bool operator()(const pair<int,double>& a, const pair<int,double>& b)const
    {
        return a.second > b.second;
    }
};
class Solution {
public:
    double maxProbability(int n, vector<vector<int>>& edges, vector<double>& dists, int start, int end) {
        vector<vector<pair<int, double>>> m(n);
        for(int i = 0; i < edges.size(); ++i) {
            auto &edge = edges[i];
            m[edge[0]].emplace_back(edge[1], dists[i]);
            m[edge[1]].emplace_back(edge[0], dists[i]);
        }

        vector<double> dis(n, 10000000);
        dis[start] = 0.0;
        
        priority_queue<pair<int, double>,vector<pair<int, double>>, cmp> q;
        q.emplace(start, 0.0);

        int i, j;
        double d, dij;
        while(!q.empty()) {
            std::tie(i, d) = q.top();
            q.pop();

            for (auto [j, pij] : m[i]) {
                if(d + dij < dis[j]) {
                    dis[j] = d + dij;
                    q.emplace(j, dis[j]);
                }
            }
        }
        return prob[end];
    }
};