做海报的网站什么编辑,文字堆积网站,wordpress无法调用主题布局和图片,淘宝优化文章目录 1. 题目描述2. 我的尝试 1. 题目描述 原题链接#xff1a;Leetcode 1514 概率最大的路径 给你一个由 n 个节点#xff08;下标从 0 开始#xff09;组成的无向加权图#xff0c;该图由一个描述边的列表组成#xff0c;其中 edges[i] [a, b] 表示连接节点 a 和 b… 文章目录 1. 题目描述2. 我的尝试 1. 题目描述 原题链接Leetcode 1514 概率最大的路径 给你一个由 n 个节点下标从 0 开始组成的无向加权图该图由一个描述边的列表组成其中 edges[i] [a, b] 表示连接节点 a 和 b 的一条无向边且该边遍历成功的概率为 succProb[i] 。
指定两个节点分别作为起点 start 和终点 end 请你找出从起点到终点成功概率最大的路径并返回其成功概率。
如果不存在从 start 到 end 的路径请 返回 0 。只要答案与标准答案的误差不超过 1e-5 就会被视作正确答案。 2. 我的尝试
该题本质上是一个单源汇最短路问题。每条边的长度就是该边遍历成功的概率两点之间的路径长度就等于该路径上各边概率的乘积。这样求 start 到 end 的最大概率就相当于求 start 到 end 的最短路。题目保证了各边概率不超过1相当于保证了无负权值的边。
求解单源汇无负权值的最短路问题可以使用dijkstra算法。本题中节点个数 n 和边的个数 m 的范围分别是 2 ≤ n ≤ 1 0 4 2 \leq n \leq10^4 2≤n≤104 和 0 ≤ m ≤ 2 ∗ 1 0 4 0 \leq m \leq 2*10^4 0≤m≤2∗104 即节点个数与边的个数数量级相当为稀疏图因此考虑使用堆优化版本的dijkstra算法。时间复杂度为 O ( m × l o g ( n ) ) O(m \times log(n)) O(m×log(n))。
const int N 1e4 10;
const int M 4e4 10;class Solution {
public:int h[N], e[M], ne[M], idx;double w[M], d[N];bool st[N];priority_queuepairdouble, int heap;void add(int a, int b, double c) {e[idx] b;w[idx] c;ne[idx] h[a];h[a] idx ;}double dijkstra(int start, int end) {for (int i 0; i end; i ) d[i] 0;d[start] 1;heap.push({1, start});while (heap.size()) {auto t heap.top();heap.pop();double dist t.first;int ver t.second;if (st[ver]) continue;st[ver] true;for (int i h[ver]; i ! -1; i ne[i]) {int j e[i];if (d[j] d[ver] * w[i]) {d[j] d[ver] * w[i];heap.push({d[j], j});}}}return d[end];}double maxProbability(int n, vectorvectorint edges, vectordouble succProb, int start_node, int end_node) {int m edges.size();memset(h, -1, sizeof h);for (int i 0; i m; i) {int a edges[i][0], b edges[i][1];double c succProb[i];add(a, b, c);add(b, a, c);}return dijkstra(start_node, end_node);}
};
