aboutsummaryrefslogtreecommitdiff
path: root/path_max_probability.c
diff options
context:
space:
mode:
Diffstat (limited to 'path_max_probability.c')
-rw-r--r--path_max_probability.c45
1 files changed, 24 insertions, 21 deletions
diff --git a/path_max_probability.c b/path_max_probability.c
index 11e2b41..0513b93 100644
--- a/path_max_probability.c
+++ b/path_max_probability.c
@@ -1,8 +1,5 @@
// 1514. Path with Maximum Probability
-#include <math.h>
-#include <stdbool.h>
-#include <stdio.h>
-#include <stdlib.h>
+#include "leetcode.h"
/*
* given an undirected weighted graph of 'n' nodes (0-indexed). represented by
@@ -14,27 +11,25 @@
* will be accepted if it differs from the correct answer by at most '1e-5'
*/
-#define LOWER_BOUND 1e-5
-
typedef struct {
int next;
double val;
} node;
void dfs(int n, bool *visited, double val, double *ans, int curr, int end,
- int *cn, node **map) {
+ int *cnt, node **map) {
if (curr == end)
*ans = fmax(*ans, val);
if (*ans >= val)
return;
- if (val - *ans <= LOWER_BOUND)
+ if (val - *ans <= 1e-5)
return;
if (visited[curr])
return;
visited[curr] = true;
- for (int i = 0; i < cn[curr]; i++) {
+ for (int i = 0; i < cnt[curr]; i++) {
double new_val = val * map[curr][i].val;
- dfs(n, visited, new_val, ans, map[curr][i].next, end, cn, map);
+ dfs(n, visited, new_val, ans, map[curr][i].next, end, cnt, map);
}
visited[curr] = false;
}
@@ -43,17 +38,17 @@ double maxProbability(int n, int **edges, int edges_size, int *edges_col_size,
double *succ_prob, int succ_prob_size, int start,
int end) {
double ans = 0;
- bool *visited = calloc(n, sizeof(bool));
- int *cn = calloc(n, sizeof(int));
- node **map = calloc(n, sizeof(node *));
+ bool *visited = (bool *)calloc(n, sizeof(bool));
+ int *cnt = (int *)calloc(n, sizeof(int));
+ node **map = (node **)calloc(n, sizeof(node *));
for (int i = 0; i < edges_size; i++) {
- cn[edges[i][0]]++;
- cn[edges[i][1]]++;
+ cnt[edges[i][0]]++;
+ cnt[edges[i][1]]++;
}
for (int i = 0; i < n; i++)
- if (cn[i])
- map[i] = malloc(cn[i] * sizeof(node));
- int *m_idx = calloc(n, sizeof(int));
+ if (cnt[i])
+ map[i] = (node *)malloc(cnt[i] * sizeof(node));
+ int *m_idx = (int *)calloc(n, sizeof(int));
for (int i = 0; i < edges_size; i++) {
int prob = edges[i][0], next = edges[i][1], idx = m_idx[prob];
map[prob][idx].next = next;
@@ -66,12 +61,20 @@ double maxProbability(int n, int **edges, int edges_size, int *edges_col_size,
map[prob][idx].val = succ_prob[i];
m_idx[prob]++;
}
- dfs(n, visited, 1.0, &ans, start, end, cn, map);
+ dfs(n, visited, 1.0, &ans, start, end, cnt, map);
free(visited);
for (int i = 0; i < n; i++)
- if (cn[i])
+ if (cnt[i])
free(map[i]);
- free(cn);
+ free(cnt);
free(map);
return ans;
}
+
+int main() {
+ int edges[3][2] = {{0, 1}, {1, 2}, {0, 2}}, edges_col_size = 3;
+ double succ_prob[] = {0.5, 0.5, 0.2};
+ printf("%f\n", maxProbability(3, (int **)edges, ARRAY_SIZE(edges),
+ &edges_col_size, succ_prob,
+ ARRAY_SIZE(succ_prob), 0, 2)); // expect: 0.2500
+}