1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
86
87
88
89
90
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);
}
|