aboutsummaryrefslogtreecommitdiff
path: root/max_path_quality_graph.c
blob: 9d3fc524e879932df149bcd75900ec8f20563887 (plain)
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);
}