diff options
Diffstat (limited to 'path_max_probability.c')
-rw-r--r-- | path_max_probability.c | 45 |
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 +} |