aboutsummaryrefslogtreecommitdiff
diff options
context:
space:
mode:
authorJack Sangdahl <[email protected]>2025-05-14 22:34:35 -0600
committerJack Sangdahl <[email protected]>2025-05-14 22:34:35 -0600
commit669b7bafe18ed3ebc31532766c489d0908882d05 (patch)
tree19adbf6c904badd1c6bfc835167dd61d26fbd22a
parent435488fe67056415982f091df0c4a4a87531e628 (diff)
downloadleetcode-669b7bafe18ed3ebc31532766c489d0908882d05.tar.gz
leetcode-669b7bafe18ed3ebc31532766c489d0908882d05.zip
2065. maximum path quality of graph
-rw-r--r--max_path_quality_graph.c91
-rw-r--r--max_path_quality_graph.py66
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,
+ )
+ )