diff options
author | Jack Sangdahl <[email protected]> | 2025-05-14 22:34:35 -0600 |
---|---|---|
committer | Jack Sangdahl <[email protected]> | 2025-05-14 22:34:35 -0600 |
commit | 669b7bafe18ed3ebc31532766c489d0908882d05 (patch) | |
tree | 19adbf6c904badd1c6bfc835167dd61d26fbd22a | |
parent | 435488fe67056415982f091df0c4a4a87531e628 (diff) | |
download | leetcode-669b7bafe18ed3ebc31532766c489d0908882d05.tar.gz leetcode-669b7bafe18ed3ebc31532766c489d0908882d05.zip |
2065. maximum path quality of graph
-rw-r--r-- | max_path_quality_graph.c | 91 | ||||
-rw-r--r-- | max_path_quality_graph.py | 66 |
2 files changed, 157 insertions, 0 deletions
diff --git a/max_path_quality_graph.c b/max_path_quality_graph.c new file mode 100644 index 0000000..9d3fc52 --- /dev/null +++ b/max_path_quality_graph.c @@ -0,0 +1,91 @@ +// 2065. Maximum Path Quality of a Graph +#include "leetcode.h" + +/* + * there is an undirected graph with 'n' nodes numbered from 0 to 'n - 1'. you + * are given a 0-indexed integer array 'values' where 'values[i]' is the value + * of the i'th node. you are also given a 0-indexed 2d integer array 'edges', + * where each 'edges[j] = [uj, vj, timej]' indicates that there is an undirected + * edge between the nodes 'uj' and 'vj', and it takes 'timej' seconds to travel + * between the two nodes. finally, you are given an integer 'maxTime'. a valid + * path in the graph is any path that starts at node 0, ends at node 0, and + * takes at most 'maxTime' seconds to complete. you may visit the same node + * multiple times. the quality of a valid path is the sum of the value of the + * unique nodes visited in the path (each node's value is added at most once to + * the sum). return the maximum quality of a valid path. + */ + +struct map { + struct map *next; + int adj; + int time; +}; + +void find_path(struct map **times, int *values, int size, int *vis, int *res, + int max, int i, int time, int max_time) { + if (time > max_time) + return; + if (!vis[i]) + max += values[i]; + if (!i) + *res = fmax(*res, max); + vis[i]++; + if (times[i]) { + struct map *curr = times[i]; + while (curr) { + int j = curr->adj, new_time = time + curr->time; + find_path(times, values, size, vis, res, max, j, new_time, max_time); + curr = curr->next; + } + } + vis[i]--; +} + +int maximalPathQuality(int *values, int valuesSize, int **edges, int edgesSize, + int *edgesColSize, int maxTime) { + if (valuesSize == 1) + return values[0]; + int *ans = (int *)malloc(sizeof(int)); + *ans = 0; + struct map **times = (struct map **)malloc(valuesSize * sizeof(struct map *)); + int *vis = (int *)malloc(valuesSize * sizeof(int)); + for (int i = 0; i < valuesSize; i++) { + times[i] = NULL; + vis[i] = 0; + } + for (int i = 0; i < edgesSize; i++) { + int src = edges[i][0], dst = edges[i][1], time = edges[i][2]; + struct map *ins1 = (struct map *)malloc(sizeof(struct map)); + ins1->adj = dst; + ins1->time = time; + ins1->next = times[src]; + times[src] = ins1; + struct map *ins2 = (struct map *)malloc(sizeof(struct map)); + ins2->adj = src; + ins2->time = time; + ins2->next = times[dst]; + times[dst] = ins2; + } + find_path(times, values, valuesSize, vis, ans, 0, 0, 0, maxTime); + return *ans; +} + +int main() { + int v1[] = {0, 32, 10, 43}, e1i[3][3] = {{0, 1, 10}, {1, 2, 15}, {0, 3, 10}}; + int v2[] = {5, 10, 15, 20}, e2i[3][3] = {{0, 1, 10}, {1, 2, 10}, {0, 3, 10}}; + int v3[] = {1, 2, 3, 4}, + e3i[4][3] = {{0, 1, 10}, {1, 2, 11}, {2, 3, 12}, {1, 3, 13}}; + struct two_d_arr e1, e2, e3; + two_d_arr_init(&e1, ARRAY_SIZE(e1i), ARRAY_SIZE(e1i[0]), e1i); + two_d_arr_init(&e2, ARRAY_SIZE(e2i), ARRAY_SIZE(e2i[0]), e2i); + two_d_arr_init(&e3, ARRAY_SIZE(e3i), ARRAY_SIZE(e3i[0]), e3i); + printf("%d\n", maximalPathQuality(v1, ARRAY_SIZE(v1), e1.arr, e1.row_size, + e1.col_size, 49)); // expect: 75 + printf("%d\n", maximalPathQuality(v1, ARRAY_SIZE(v1), e1.arr, e1.row_size, + e1.col_size, 30)); // expect: 25 + printf("%d\n", maximalPathQuality(v1, ARRAY_SIZE(v1), e1.arr, e1.row_size, + e1.col_size, 50)); // expect: 50 + two_d_arr_free(&e1); + two_d_arr_free(&e2); + two_d_arr_free(&e3); +} diff --git a/max_path_quality_graph.py b/max_path_quality_graph.py new file mode 100644 index 0000000..fcf4ee9 --- /dev/null +++ b/max_path_quality_graph.py @@ -0,0 +1,66 @@ +# 2065. Maximum Path Quality of a Graph +from collections import defaultdict + +""" +there is an undirected graph with 'n' nodes numbered from 0 to 'n - 1'. you +are given a 0-indexed integer array 'values' where 'values[i]' is the value +of the i'th node. you are also given a 0-indexed 2d integer array 'edges', +where each 'edges[j] = [uj, vj, timej]' indicates that there is an undirected +edge between the nodes 'uj' and 'vj', and it takes 'timej' seconds to travel +between the two nodes. finally, you are given an integer 'maxTime'. a valid +path in the graph is any path that starts at node 0, ends at node 0, and +takes at most 'maxTime' seconds to complete. you may visit the same node +multiple times. the quality of a valid path is the sum of the value of the +unique nodes visited in the path (each node's value is added at most once to +the sum). return the maximum quality of a valid path. +""" + + +class Solution(object): + def maximalPathQuality(self, values, edges, maxTime): + """ + :type values: List[int] + :type edges: List[List[int]] + :type maxTime: int + :rtype: int + """ + graph = defaultdict(list) + for u, v, t in edges: + graph[u].append((v, t)) + graph[v].append((u, t)) + + def dfs(node, vis, gain, cost): + if node == 0: + self.ans = max(self.ans, gain) + for i, t in graph[node]: + if t <= cost: + dfs(i, vis | set([i]), gain + (i not in vis) * values[i], cost - t) + + self.ans = 0 + dfs(0, set([0]), values[0], maxTime) + return self.ans + + +if __name__ == "__main__": + obj = Solution() + print( + obj.maximalPathQuality( + values=[0, 32, 10, 43], + edges=[[0, 1, 10], [1, 2, 15], [0, 3, 10]], + maxTime=49, + ) + ) + print( + obj.maximalPathQuality( + values=[5, 10, 15, 20], + edges=[[0, 1, 10], [1, 2, 10], [0, 3, 10]], + maxTime=30, + ) + ) + print( + obj.maximalPathQuality( + values=[1, 2, 3, 4], + edges=[[0, 1, 10], [1, 2, 11], [2, 3, 12], [1, 3, 13]], + maxTime=50, + ) + ) |