aboutsummaryrefslogtreecommitdiff
path: root/min_fuel_report_captial.c
blob: afa0ba16ab114e2bc810027dacaad5b2fc0d22e9 (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
// 2477. Minimum Fuel Cost to Report to the Capital
#include <stdio.h>
#include <stdlib.h>

/*
 * there is a tree (ie. a connected, undirected graph with no cycles) structure
 * country network consisting of 'n' cities numbered from 0 to 'n - 1' and
 * exactly 'n - 1' roads the capital city is city 0. given a 2d integer array
 * 'roads' where 'roads[i] = [ai, bi]' denotes that there exists a bidirectional
 * road connecting cities ai & bi. there is a meeting for the representitive of
 * each city. the meeting is in the capital city. there is a car in each city.
 * given integer seats that indicates the number of seats in each car. a
 * representitive can use the car in their city to travel or change the car and
 * ride with another representitive. the cost of traveling between two cities is
 * 1 liter of fuel. return minimum number of liters of fuel needed to reach
 * capital city.
 */

void dfs(int seats, int from, int now, long long *ans, int **can_go, int *cnt,
         int *ppl) {
  if (cnt[now] == 1) {
    *ppl = 1;
    return;
  }
  int next = 0, next_city = 0;
  for (int i = 0; i < cnt[now]; i++) {
    if (can_go[now][i] == from) {
      i++;
      while (i < cnt[now]) {
        dfs(seats, now, can_go[now][i], ans, can_go, cnt, &next_city);
        *ans += next_city / seats;
        if (next_city % seats != 0)
          *ans += 1;
        next += next_city;
        i++;
      }
    } else {
      dfs(seats, now, can_go[now][i], ans, can_go, cnt, &next_city);
      *ans += next_city / seats;
      if (next_city % seats != 0)
        *ans += 1;
      next += next_city;
    }
  }
  *ppl = next + 1;
  return;
}

long long minimumFuelCost(int **roads, int roadsSize, int *roadsColSize,
                          int seats) {
  int **can_go = malloc(sizeof(int *) * (roadsSize + 1));
  for (int i = 0; i <= roadsSize; i++)
    can_go[i] = malloc(sizeof(int) * 20);
  int *cnt = calloc((roadsSize + 1), sizeof(int));
  for (int i = 0; i < roadsSize; i++) {
    can_go[roads[i][0]][cnt[roads[i][0]]] = roads[i][1];
    can_go[roads[i][1]][cnt[roads[i][1]]] = roads[i][0];
    cnt[roads[i][0]]++;
    cnt[roads[i][1]]++;
  }
  long long ans = 0;
  int ppl = 0;
  for (int i = 0; i < cnt[0]; i++) {
    dfs(seats, 0, can_go[0][i], &ans, can_go, cnt, &ppl);
    ans += (ppl / seats);
    if (ppl % seats != 0)
      ans += 1;
  }
  free(cnt);
  for (int i = 0; i <= roadsSize; i++)
    free(can_go[i]);
  free(can_go);
  return ans;
}

int main() {
  int roads1[3][2] = {{0, 1}, {0, 2}, {0, 3}};
  int rs1 = 3;
  int rcs1[] = {3};
  int seats1 = 5;
  printf("%lld\n", minimumFuelCost(roads1, rs1, rcs1, seats1));
}