Сложность: medium
Вам дан неориентированный взвешенный граф из n узлов (индексация с нуля), представленный списком ребер, где edges[i] = [a, b] является неориентированным ребром, соединяющим узлы a и b с вероятностью успешного прохождения этого ребра succProb[i].
Даны два узла start и end, найдите путь с максимальной вероятностью успеха, чтобы перейти от start к end, и верните его вероятность успеха.
Если пути от start до end не существует, верните 0. Ваш ответ будет принят, если он отличается от правильного ответа не более чем на 1e-5.
Пример:
Input: n = 3, edges = [[0,1],[1,2],[0,2]], succProb = [0.5,0.5,0.2], start = 0, end = 2
Output: 0.25000
Explanation: There are two paths from start to end, one having a probability of success = 0.2 and the other has 0.5 * 0.5 = 0.25.
👨💻 Алгоритм:
1⃣Инициализируйте массив maxProb как максимальную вероятность достижения каждого узла из начального узла, установите maxProb[start] равным 1.
2⃣Расслабьте все ребра: для каждого ребра (u, v), если найдена более высокая вероятность достижения u через это ребро, обновите max_prob[u] как max_prob[u] = max_prob[v] * path_prob. Если найдена более высокая вероятность достижения v через это ребро, обновите max_prob[v].
3⃣Если нам не удается обновить какой-либо узел с более высокой вероятностью, мы можем остановить итерацию, перейдя к шагу 4. В противном случае повторяйте шаг 2, пока все ребра не будут расслаблены n - 1 раз.
Верните max_prob[end].
😎 Решение:
class Solution {
public:
double maxProbability(int n, vector<vector<int>>& edges, vector<double>& succProb, int start, int end) {
vector<double> maxProb(n, 0.0);
maxProb[start] = 1.0;
for (int i = 0; i < n - 1; i++) {
bool hasUpdate = false;
for (int j = 0; j < edges.size(); j++) {
int u = edges[j][0];
int v = edges[j][1];
double pathProb = succProb[j];
if (maxProb[u] * pathProb > maxProb[v]) {
maxProb[v] = maxProb[u] * pathProb;
hasUpdate = true;
}
if (maxProb[v] * pathProb > maxProb[u]) {
maxProb[u] = maxProb[v] * pathProb;
hasUpdate = true;
}
}
if (!hasUpdate) {
break;
}
}
return maxProb[end];
}
};Ставь 👍 и забирай 📚 Базу знаний