leetcode

// 2045. Second Minimum Time to Reach Destination
#include "leetcode.h"

/*
 * a city is represented as a bi directional connected graph with 'n' vertices
 * where each vertex is labeled from 1 to 'n' inclusively. the edges in the
 * graph are represented as a 2d integer array 'edges' where each 'edges[i] =
 * [ui, vi]' denotes a bi directional edge between vertex 'ui' and vertex 'vi'.
 * every vertex pair is connected by at most one edge, and no vertex has an edge
 * to itself. the time taken to traverse any edge is 'time' minutes. each vertex
 * has a traffic signal which changes its colour from green to red and vice
 * versa every 'change' minutes. all signals change at the same time. you can
 * entre a vertex at any time, but can leave a vertex only when the signal is
 * green. you cannot wait at a vertex if the signal is green.
 */

struct state {
  int node;
  int time;
};

struct min_heap {
  struct state *data;
  int size;
  int capacity;
};

void swap(struct state *a, struct state *b) {
  struct state tmp = *a;
  *a = *b;
  *b = tmp;
}

struct min_heap *create_min_heap(int capacity) {
  struct min_heap *heap = (struct min_heap *)malloc(sizeof(struct min_heap));
  heap->data = (struct state *)malloc(capacity * sizeof(struct state));
  heap->size = 0;
  heap->capacity = capacity;
  return heap;
}

void min_heapify(struct min_heap *heap, int idx) {
  int smallest = idx, left = 2 * idx + 1, right = 2 * idx + 2;
  if (left < heap->size && heap->data[left].time < heap->data[smallest].time)
    smallest = left;
  if (right < heap->size && heap->data[right].time < heap->data[smallest].time)
    smallest = right;
  if (smallest != idx) {
    swap(&heap->data[idx], &heap->data[smallest]);
    min_heapify(heap, smallest);
  }
}

struct state extract_min(struct min_heap *heap) {
  if (heap->size <= 0)
    return (struct state){-1, -1};
  if (heap->size == 1) {
    heap->size--;
    return heap->data[0];
  }
  struct state root = heap->data[0];
  heap->data[0] = heap->data[heap->size - 1];
  heap->size--;
  min_heapify(heap, 0);
  return root;
}

void insert_min_heap(struct min_heap *heap, struct state k) {
  if (heap->size == heap->capacity) {
    heap->capacity *= 2;
    heap->data = (struct state *)realloc(heap->data,
                                         heap->capacity * sizeof(struct state));
  }
  heap->size++;
  int i = heap->size - 1;
  heap->data[i] = k;
  while (i && heap->data[(i - 1) / 2].time > heap->data[i].time) {
    swap(&heap->data[i], &heap->data[(i - 1) / 2]);
    i = (i - 1) / 2;
  }
}

void free_min_heap(struct min_heap *heap) {
  free(heap->data);
  free(heap);
}

struct node {
  int val;
  struct node *next;
};

struct graph {
  struct node **heads;
  int *sizes;
  int size;
};

struct graph *create_graph(int n) {
  struct graph *g = (struct graph *)malloc(sizeof(struct graph));
  g->heads = (struct node **)malloc((n + 1) * sizeof(struct node *));
  g->sizes = (int *)calloc(n + 1, sizeof(int));
  g->size = n;
  for (int i = 0; i <= n; i++)
    g->heads[i] = NULL;
  return g;
}

void add_edges(struct graph *g, int u, int v) {
  struct node *n = (struct node *)malloc(sizeof(struct node));
  n->val = v;
  n->next = g->heads[u];
  g->heads[u] = n;
  n = (struct node *)malloc(sizeof(struct node));
  n->val = u;
  n->next = g->heads[v];
  g->heads[v] = n;
  g->sizes[u]++;
  g->sizes[v]++;
}

void free_graph(struct graph *g) {
  for (int i = 0; i <= g->size; i++) {
    struct node *head = g->heads[i];
    while (head) {
      struct node *tmp = head;
      head = head->next;
      free(tmp);
    }
  }
  free(g->heads);
  free(g->sizes);
  free(g);
}

int secondMinimum(int n, int **edges, int edgesSize, int *edgesColSize,
                  int time, int change) {
  struct graph *g = create_graph(n);
  for (int i = 0; i < edgesSize; i++)
    add_edges(g, edges[i][0], edges[i][1]);
  int *min_time = (int *)malloc((n + 1) * sizeof(int));
  int *second_min_time = (int *)malloc((n + 1) * sizeof(int));
  for (int i = 0; i <= n; i++) {
    min_time[i] = INT_MAX;
    second_min_time[i] = INT_MAX;
  }
  struct min_heap *pq = create_min_heap(edgesSize * 2);
  insert_min_heap(pq, (struct state){1, 0});
  min_time[1] = 0;
  while (pq->size) {
    struct state curr = extract_min(pq);
    int curr_node = curr.node;
    int curr_time = curr.time;
    struct node *neighbour_node = g->heads[curr_node];
    while (neighbour_node) {
      int neighbour = neighbour_node->val, wait_time = 0;
      if ((curr_time / change) % 2 == 1)
        wait_time = change = (curr_time % change);
      int next_time = curr_time + time + wait_time;
      if (next_time < min_time[neighbour]) {
        second_min_time[neighbour] = min_time[neighbour];
        min_time[neighbour] = next_time;
        insert_min_heap(pq, (struct state){neighbour, next_time});
      } else if (next_time > min_time[neighbour] &&
                 next_time < second_min_time[neighbour]) {
        second_min_time[neighbour] = next_time;
        insert_min_heap(pq, (struct state){neighbour, next_time});
      }
      neighbour_node = neighbour_node->next;
    }
  }
  int ans = second_min_time[n];
  free(min_time), free(second_min_time);
  free_min_heap(pq);
  free_graph(g);
  return ans;
}

int main() {
  int e1[5][2] = {{1, 2}, {1, 3}, {1, 4}, {3, 4}, {4, 5}}, e2[1][2] = {{1, 2}};
  int ecs1 = 5, ecs2 = 1;
  printf("%d\n", secondMinimum(5, (int **)e1, ARRAY_SIZE(e1), &ecs1, 3,
                               5)); // expect: 13
  printf("%d\n", secondMinimum(2, (int **)e2, ARRAY_SIZE(e2), &ecs2, 3,
                               2)); // expect: 11
}