Leetcode 1514. 概率最大的路径

地址 https://leetcode-cn.com/problems/path-with-maximum-probability/

给你一个由 n 个节点（下标从 0 开始）组成的无向加权图，该图由一个描述边的列表组成，
其中 edges[i] = [a, b] 表示连接节点 a 和 b 的一条无向边，且该边遍历成功的概率为 succProb[i] 。
指定两个节点分别作为起点 start 和终点 end ，请你找出从起点到终点成功概率最大的路径，并返回其成功概率。
如果不存在从 start 到 end 的路径，请 返回 0 。只要答案与标准答案的误差不超过 1e-5 ，就会被视作正确答案。

示例 1：

输入：n = 3, edges = [[0,1],[1,2],[0,2]], succProb = [0.5,0.5,0.2], start = 0, end = 2
输出：0.25000
解释：从起点到终点有两条路径，其中一条的成功概率为 0.2 ，而另一条为 0.5 * 0.5 = 0.25


示例 2：

输入：n = 3, edges = [[0,1],[1,2],[0,2]], succProb = [0.5,0.5,0.3], start = 0, end = 2
输出：0.30000




示例 3：

输入：n = 3, edges = [[0,1]], succProb = [0.5], start = 0, end = 2
输出：0.00000
解释：节点 0 和 节点 2 之间不存在路径
 

提示：

2 <= n <= 10^4
0 <= start, end < n
start != end
0 <= a, b < n
a != b
0 <= succProb.length == edges.length <= 2*10^4
0 <= succProb[i] <= 1
每两个节点之间最多有一条边

解答
dijkstra变形
1 求最短边也就是距离相加要更换成最大概率的乘积。
2 题目给出的边和边的概率要更换成自己习惯的图的构造方式

class Solution {
public:
	typedef pair PII;
	//构造图
	vector> g[20010];
	double dist[20010];
	bool st[20010];
	void init() {
		memset(st, 0, sizeof st);
		for (int i = 0; i < 20010; i++) {
			dist[i] = 0.0;
		}
	}
	double maxProbability(int n, vector>& edges, vector& succProb, int start, int end) {
		for (int i = 0; i < edges.size(); i++) {
			int a = edges[i][0]; int b = edges[i][1]; double eg = succProb[i];
			g[a].push_back({ eg,b });
			g[b].push_back({ eg,a });
		}
		init();

		dist[start] = 1.0;
		priority_queue, less> heap;
		heap.push({ 1.0, start });      // first存储距离*，second存储节点编号

		while (heap.size()) {
			auto t = heap.top();
			heap.pop();

			int ver = t.second; double distance = t.first;

			if (st[ver]) continue;
			st[ver] = true;

			for (int i = 0; i < g[ver].size(); i++) {
				double jp = g[ver][i].first;
				int jn = g[ver][i].second;
				if (dist[ver] * jp - dist[jn] > 1e-5) {
					dist[jn] = dist[ver] * jp;
					heap.push({ dist[jn],jn });
				}
			}
		}

		if (dist[end] == 0.0) return 0.0;
		return dist[end];
	}
};

我的视频题解空间