Language: C

#include <assert.h>
#include <stdbool.h>
#include <stdint.h>
#include <stdio.h>
#include <stdlib.h>
#include <string.h>

void *xmalloc(size_t size) {
  void *ptr = malloc(size);
  if (ptr == NULL) {
    fprintf(stderr, "Failed to allocate memory\n");
    exit(EXIT_FAILURE);
  }
  return ptr;
}

typedef struct {
  void **data;
  size_t capacity;
  size_t len;
} Vector;

#define VECTOR_DEFAULT_CAPACITY 16

Vector *new_vec_with(size_t capacity) {
  Vector *v = xmalloc(sizeof(Vector));
  v->data = xmalloc(sizeof(void *) * capacity);
  memset(v->data, 0, sizeof(void *) * capacity);
  v->capacity = capacity;
  v->len = 0;
  return v;
}

Vector *new_vec() { return new_vec_with(VECTOR_DEFAULT_CAPACITY); }

void vec_expand(Vector *v, size_t size) {
  if (v->len < size) {
    v->capacity = size;
    v->len = size;
    v->data = realloc(v->data, sizeof(void *) * v->capacity);
  }
}

void vec_push(Vector *v, void *elem) {
  if (v->len == v->capacity) {
    v->capacity *= 2;
    v->data = realloc(v->data, sizeof(void *) * v->capacity);
  }
  v->data[v->len++] = elem;
}

void *vec_pop(Vector *v) {
  assert(v->len);
  return v->data[--v->len];
}

#define VecForeachWithType(vec, T, loop_val, loop_body)                        \
  for (size_t fe_loop_counter_##vec = 0; fe_loop_counter_##vec < vec->len;     \
       fe_loop_counter_##vec++) {                                              \
    T loop_val = vec->data[fe_loop_counter_##vec];                             \
    loop_body;                                                                 \
  }

#define VecForeach(vec, loop_val, loop_body)                                   \
  VecForeachWithType(vec, void *, loop_val, loop_body)

typedef int (*ELEM_COMPARE)(void *, void *);

typedef struct {
  Vector *vec;
  ELEM_COMPARE compare;
} BinaryHeap;

#define GetHeapVec(heap) (heap->vec)
#define GetHeapData(heap, i) (heap->vec->data[i])

BinaryHeap *new_BinaryHeap(ELEM_COMPARE compare) {
  BinaryHeap *heap = xmalloc(sizeof(BinaryHeap));
  heap->vec = new_vec();
  heap->compare = compare;
  return heap;
}

void heap_insert(BinaryHeap *heap, void *val) {
  size_t n = GetHeapVec(heap)->len;
  vec_push(GetHeapVec(heap), val);

  while (n != 0) {
    size_t i = (n - 1) / 2;

    // heap->vec->data[n] > heap->vec->data[i]
    if (heap->compare(GetHeapData(heap, n), GetHeapData(heap, i)) == 1) {
      void *tmp = GetHeapData(heap, n);
      GetHeapData(heap, n) = GetHeapData(heap, i);
      GetHeapData(heap, i) = tmp;
    }

    n = i;
  }
}

void *heap_pop(BinaryHeap *heap) {
  assert(GetHeapVec(heap)->len > 0);

  size_t n = GetHeapVec(heap)->len - 1;
  void *ret = GetHeapData(heap, 0);
  GetHeapData(heap, 0) = GetHeapData(heap, n);
  vec_pop(GetHeapVec(heap));

  for (size_t i = 0, j; (j = 2 * i + 1) < n;) {
    if ((j != n - 1) &&
        heap->compare(GetHeapData(heap, j), GetHeapData(heap, j + 1)) == -1) {
      j++;
    }

    if (heap->compare(GetHeapData(heap, i), GetHeapData(heap, j)) == -1) {
      void *tmp = GetHeapData(heap, j);
      GetHeapData(heap, j) = GetHeapData(heap, i);
      GetHeapData(heap, i) = tmp;
    }

    i = j;
  }

  return ret;
}

bool heap_empty(BinaryHeap *heap) { return GetHeapVec(heap)->len == 0; }

typedef struct {
  BinaryHeap *heap;
} PriorityQueue;

PriorityQueue *new_PriorityQueue(ELEM_COMPARE compare) {
  PriorityQueue *pqueue = xmalloc(sizeof(PriorityQueue));
  pqueue->heap = new_BinaryHeap(compare);
  return pqueue;
}

void pqueue_push(PriorityQueue *pqueue, void *elem) {
  heap_insert(pqueue->heap, elem);
}

void *pqueue_pop(PriorityQueue *pqueue) { return heap_pop(pqueue->heap); }

bool pqueue_empty(PriorityQueue *pqueue) { return heap_empty(pqueue->heap); }

const int INF = 1 << 30;

typedef struct {
  int dst;
  int cost;
} Edge;

Edge *new_Edge(int dst, int cost) {
  Edge *edge = xmalloc(sizeof(Edge));
  edge->dst = dst;
  edge->cost = cost;
  return edge;
}

static int cmp_Edge(void *lhs, void *rhs) {
  Edge *le = (Edge *)lhs;
  Edge *re = (Edge *)rhs;

  if (le->cost >= re->cost) {
    return 1;
  } else {
    return -1;
  }
}

#define INT_TO_VoPTR(i) ((void *)(intptr_t)i)
#define VoPTR_TO_INT(ptr) ((int)(intptr_t)ptr)

Vector *dijkstra(Vector *tree, int src) {
  int V = tree->len;
  Vector *dist = new_vec_with(V);
  for (size_t i = 0; i < V; i++) {
    dist->data[i] = INT_TO_VoPTR(INF);
  }

  PriorityQueue *pqueue = new_PriorityQueue(cmp_Edge);

  dist->data[src] = 0;
  pqueue_push(pqueue, new_Edge(src, 0));

  while (!pqueue_empty(pqueue)) {
    Edge *e = pqueue_pop(pqueue);
    int v = e->dst, cost = e->cost;
    free(e);

    if (VoPTR_TO_INT(dist->data[v]) < cost) {
      continue;
    }

    Vector *vec = tree->data[v];
    VecForeachWithType(vec, Edge *, e, {
      if (VoPTR_TO_INT(dist->data[v]) + e->cost <
          VoPTR_TO_INT(dist->data[e->dst])) {
        dist->data[e->dst] =
            INT_TO_VoPTR(VoPTR_TO_INT(dist->data[v]) + e->cost);
        pqueue_push(pqueue, new_Edge(e->dst, VoPTR_TO_INT(dist->data[e->dst])));
      }
    });
  }

  return dist;
}

int main(void) {
  int V, E, r;
  scanf("%d%d%d", &V, &E, &r);

  Vector *tree = new_vec();
  for (size_t i = 0; i < V; i++) {
    vec_push(tree, new_vec());
  }

  for (int i = 0; i < E; i++) {
    int s, t, d;
    scanf("%d%d%d", &s, &t, &d);
    vec_push(tree->data[s], new_Edge(t, d));
  }

  Vector *ret = dijkstra(tree, r);

  for (size_t i = 0; i < V; i++) {
    Vector *v = tree->data[i];
    for (size_t j = 0; j < v->len; j++) {
      free(v->data[j]);
    }
    free(v);
  }

  for (int i = 0; i < V; i++) {
    int result = VoPTR_TO_INT(ret->data[i]);
    if (result >= INF) {
      printf("INF\n");
    } else {
      printf("%ld\n", result);
    }
  }

  return 0;
}
#include <assert.h>
#include <stdbool.h>
#include <stdint.h>
#include <stdio.h>
#include <stdlib.h>
#include <string.h>

void *xmalloc(size_t size) {
  void *ptr = malloc(size);
  if (ptr == NULL) {
    fprintf(stderr, "Failed to allocate memory\n");
    exit(EXIT_FAILURE);
  }
  return ptr;
}

typedef struct {
  void **data;
  size_t capacity;
  size_t len;
} Vector;

#define VECTOR_DEFAULT_CAPACITY 16

Vector *new_vec_with(size_t capacity) {
  Vector *v = xmalloc(sizeof(Vector));
  v->data = xmalloc(sizeof(void *) * capacity);
  memset(v->data, 0, sizeof(void *) * capacity);
  v->capacity = capacity;
  v->len = 0;
  return v;
}

Vector *new_vec() { return new_vec_with(VECTOR_DEFAULT_CAPACITY); }

void vec_expand(Vector *v, size_t size) {
  if (v->len < size) {
    v->capacity = size;
    v->len = size;
    v->data = realloc(v->data, sizeof(void *) * v->capacity);
  }
}

void vec_push(Vector *v, void *elem) {
  if (v->len == v->capacity) {
    v->capacity *= 2;
    v->data = realloc(v->data, sizeof(void *) * v->capacity);
  }
  v->data[v->len++] = elem;
}

void *vec_pop(Vector *v) {
  assert(v->len);
  return v->data[--v->len];
}

#define VecForeachWithType(vec, T, loop_val, loop_body)                        \
  for (size_t fe_loop_counter_##vec = 0; fe_loop_counter_##vec < vec->len;     \
       fe_loop_counter_##vec++) {                                              \
    T loop_val = vec->data[fe_loop_counter_##vec];                             \
    loop_body;                                                                 \
  }

#define VecForeach(vec, loop_val, loop_body)                                   \
  VecForeachWithType(vec, void *, loop_val, loop_body)

typedef int (*ELEM_COMPARE)(void *, void *);

typedef struct {
  Vector *vec;
  ELEM_COMPARE compare;
} BinaryHeap;

#define GetHeapVec(heap) (heap->vec)
#define GetHeapData(heap, i) (heap->vec->data[i])

BinaryHeap *new_BinaryHeap(ELEM_COMPARE compare) {
  BinaryHeap *heap = xmalloc(sizeof(BinaryHeap));
  heap->vec = new_vec();
  heap->compare = compare;
  return heap;
}

void heap_insert(BinaryHeap *heap, void *val) {
  size_t n = GetHeapVec(heap)->len;
  vec_push(GetHeapVec(heap), val);

  while (n != 0) {
    size_t i = (n - 1) / 2;

    // heap->vec->data[n] > heap->vec->data[i]
    if (heap->compare(GetHeapData(heap, n), GetHeapData(heap, i)) == 1) {
      void *tmp = GetHeapData(heap, n);
      GetHeapData(heap, n) = GetHeapData(heap, i);
      GetHeapData(heap, i) = tmp;
    }

    n = i;
  }
}

void *heap_pop(BinaryHeap *heap) {
  assert(GetHeapVec(heap)->len > 0);

  size_t n = GetHeapVec(heap)->len - 1;
  void *ret = GetHeapData(heap, 0);
  GetHeapData(heap, 0) = GetHeapData(heap, n);
  vec_pop(GetHeapVec(heap));

  for (size_t i = 0, j; (j = 2 * i + 1) < n;) {
    if ((j != n - 1) &&
        heap->compare(GetHeapData(heap, j), GetHeapData(heap, j + 1)) == -1) {
      j++;
    }

    if (heap->compare(GetHeapData(heap, i), GetHeapData(heap, j)) == -1) {
      void *tmp = GetHeapData(heap, j);
      GetHeapData(heap, j) = GetHeapData(heap, i);
      GetHeapData(heap, i) = tmp;
    }

    i = j;
  }

  return ret;
}

bool heap_empty(BinaryHeap *heap) { return GetHeapVec(heap)->len == 0; }

typedef struct {
  BinaryHeap *heap;
} PriorityQueue;

PriorityQueue *new_PriorityQueue(ELEM_COMPARE compare) {
  PriorityQueue *pqueue = xmalloc(sizeof(PriorityQueue));
  pqueue->heap = new_BinaryHeap(compare);
  return pqueue;
}

void pqueue_push(PriorityQueue *pqueue, void *elem) {
  heap_insert(pqueue->heap, elem);
}

void *pqueue_pop(PriorityQueue *pqueue) { return heap_pop(pqueue->heap); }

bool pqueue_empty(PriorityQueue *pqueue) { return heap_empty(pqueue->heap); }

const int INF = 1 << 30;

typedef struct {
  int dst;
  int cost;
} Edge;

Edge *new_Edge(int dst, int cost) {
  Edge *edge = xmalloc(sizeof(Edge));
  edge->dst = dst;
  edge->cost = cost;
  return edge;
}

static int cmp_Edge(void *lhs, void *rhs) {
  Edge *le = (Edge *)lhs;
  Edge *re = (Edge *)rhs;

  if (le->cost >= re->cost) {
    return 1;
  } else {
    return -1;
  }
}

#define INT_TO_VoPTR(i) ((void *)(intptr_t)i)
#define VoPTR_TO_INT(ptr) ((int)(intptr_t)ptr)

Vector *dijkstra(Vector *tree, int src) {
  int V = tree->len;
  Vector *dist = new_vec_with(V);
  for (size_t i = 0; i < V; i++) {
    dist->data[i] = INT_TO_VoPTR(INF);
  }

  PriorityQueue *pqueue = new_PriorityQueue(cmp_Edge);

  dist->data[src] = 0;
  pqueue_push(pqueue, new_Edge(src, 0));

  while (!pqueue_empty(pqueue)) {
    Edge *e = pqueue_pop(pqueue);
    int v = e->dst, cost = e->cost;
    free(e);

    if (VoPTR_TO_INT(dist->data[v]) < cost) {
      continue;
    }

    Vector *vec = tree->data[v];
    VecForeachWithType(vec, Edge *, e, {
      if (VoPTR_TO_INT(dist->data[v]) + e->cost <
          VoPTR_TO_INT(dist->data[e->dst])) {
        dist->data[e->dst] =
            INT_TO_VoPTR(VoPTR_TO_INT(dist->data[v]) + e->cost);
        pqueue_push(pqueue, new_Edge(e->dst, VoPTR_TO_INT(dist->data[e->dst])));
      }
    });
  }

  return dist;
}

int main(void) {
  int V, E, r;
  scanf("%d%d%d", &V, &E, &r);

  Vector *tree = new_vec();
  for (size_t i = 0; i < V; i++) {
    vec_push(tree, new_vec());
  }

  for (int i = 0; i < E; i++) {
    int s, t, d;
    scanf("%d%d%d", &s, &t, &d);
    vec_push(tree->data[s], new_Edge(t, d));
  }

  Vector *ret = dijkstra(tree, r);

  for (size_t i = 0; i < V; i++) {
    Vector *v = tree->data[i];
    for (size_t j = 0; j < v->len; j++) {
      free(v->data[j]);
    }
    free(v);
  }

  for (int i = 0; i < V; i++) {
    int result = VoPTR_TO_INT(ret->data[i]);
    if (result >= INF) {
      printf("INF\n");
    } else {
      printf("%ld\n", result);
    }
  }

  return 0;
}



Compiler output:
main.c:254:7: error: redefinition of 'xmalloc'
  254 | void *xmalloc(size_t size) {
      |       ^~~~~~~
main.c:8:7: note: previous definition of 'xmalloc' with type 'void *(size_t)' {aka 'void *(long unsigned int)'}
    8 | void *xmalloc(size_t size) {
      |       ^~~~~~~
main.c:267:3: error: conflicting types for 'Vector'; have 'struct <anonymous>'
  267 | } Vector;
      |   ^~~~~~
main.c:21:3: note: previous declaration of 'Vector' with type 'Vector'
   21 | } Vector;
      |   ^~~~~~
main.c:271:9: error: conflicting types for 'new_vec_with'; have 'Vector *(size_t)' {aka 'Vector *(long unsigned int)'}
  271 | Vector *new_vec_with(size_t capacity) {
      |         ^~~~~~~~~~~~
main.c:25:9: note: previous definition of 'new_vec_with' with type 'Vector *(size_t)' {aka 'Vector *(long unsigned int)'}
   25 | Vector *new_vec_with(size_t capacity) {
      |         ^~~~~~~~~~~~
main.c:280:9: error: conflicting types for 'new_vec'; have 'Vector *()'
  280 | Vector *new_vec() { return new_vec_with(VECTOR_DEFAULT_CAPACITY); }
      |         ^~~~~~~
main.c:34:9: note: previous definition of 'new_vec' with type 'Vector *()'
   34 | Vector *new_vec() { return new_vec_with(VECTOR_DEFAULT_CAPACITY); }
      |         ^~~~~~~
main.c:282:6: error: conflicting types for 'vec_expand'; have 'void(Vector *, size_t)' {aka 'void(Vector *, long unsigned int)'}
  282 | void vec_expand(Vector *v, size_t size) {
      |      ^~~~~~~~~~
main.c:36:6: note: previous definition of 'vec_expand' with type 'void(Vector *, size_t)' {aka 'void(Vector *, long unsigned int)'}
   36 | void vec_expand(Vector *v, size_t size) {
      |      ^~~~~~~~~~
main.c:290:6: error: conflicting types for 'vec_push'; have 'void(Vector *, void *)'
  290 | void vec_push(Vector *v, void *elem) {
      |      ^~~~~~~~
main.c:44:6: note: previous definition of 'vec_push' with type 'void(Vector *, void *)'
   44 | void vec_push(Vector *v, void *elem) {
      |      ^~~~~~~~
main.c:298:7: error: conflicting types for 'vec_pop'; have 'void *(Vector *)'
  298 | void *vec_pop(Vector *v) {
      |       ^~~~~~~
main.c:52:7: note: previous definition of 'vec_pop' with type 'void *(Vector *)'
   52 | void *vec_pop(Vector *v) {
      |       ^~~~~~~
main.c:318:3: error: conflicting types for 'BinaryHeap'; have 'struct <anonymous>'
  318 | } BinaryHeap;
      |   ^~~~~~~~~~
main.c:72:3: note: previous declaration of 'BinaryHeap' with type 'BinaryHeap'
   72 | } BinaryHeap;
      |   ^~~~~~~~~~
main.c:323:13: error: conflicting types for 'new_BinaryHeap'; have 'BinaryHeap *(int (*)(void *, void *))'
  323 | BinaryHeap *new_BinaryHeap(ELEM_COMPARE compare) {
      |             ^~~~~~~~~~~~~~
main.c:77:13: note: previous definition of 'new_BinaryHeap' with type 'BinaryHeap *(int (*)(void *, void *))'
   77 | BinaryHeap *new_BinaryHeap(ELEM_COMPARE compare) {
      |             ^~~~~~~~~~~~~~
main.c:330:6: error: conflicting types for 'heap_insert'; have 'void(BinaryHeap *, void *)'
  330 | void heap_insert(BinaryHeap *heap, void *val) {
      |      ^~~~~~~~~~~
main.c:84:6: note: previous definition of 'heap_insert' with type 'void(BinaryHeap *, void *)'
   84 | void heap_insert(BinaryHeap *heap, void *val) {
      |      ^~~~~~~~~~~
main.c:348:7: error: conflicting types for 'heap_pop'; have 'void *(BinaryHeap *)'
  348 | void *heap_pop(BinaryHeap *heap) {
      |       ^~~~~~~~
main.c:102:7: note: previous definition of 'heap_pop' with type 'void *(BinaryHeap *)'
  102 | void *heap_pop(BinaryHeap *heap) {
      |       ^~~~~~~~
main.c:374:6: error: conflicting types for 'heap_empty'; have '_Bool(BinaryHeap *)'
  374 | bool heap_empty(BinaryHeap *heap) { return GetHeapVec(heap)->len == 0; }
      |      ^~~~~~~~~~
main.c:128:6: note: previous definition of 'heap_empty' with type '_Bool(BinaryHeap *)'
  128 | bool heap_empty(BinaryHeap *heap) { return GetHeapVec(heap)->len == 0; }
      |      ^~~~~~~~~~
main.c:378:3: error: conflicting types for 'PriorityQueue'; have 'struct <anonymous>'
  378 | } PriorityQueue;
      |   ^~~~~~~~~~~~~
main.c:132:3: note: previous declaration of 'PriorityQueue' with type 'PriorityQueue'
  132 | } PriorityQueue;
      |   ^~~~~~~~~~~~~
main.c:380:16: error: conflicting types for 'new_PriorityQueue'; have 'PriorityQueue *(int (*)(void *, void *))'
  380 | PriorityQueue *new_PriorityQueue(ELEM_COMPARE compare) {
      |                ^~~~~~~~~~~~~~~~~
main.c:134:16: note: previous definition of 'new_PriorityQueue' with type 'PriorityQueue *(int (*)(void *, void *))'
  134 | PriorityQueue *new_PriorityQueue(ELEM_COMPARE compare) {
      |                ^~~~~~~~~~~~~~~~~
main.c:386:6: error: conflicting types for 'pqueue_push'; have 'void(PriorityQueue *, void *)'
  386 | void pqueue_push(PriorityQueue *pqueue, void *elem) {
      |      ^~~~~~~~~~~
main.c:140:6: note: previous definition of 'pqueue_push' with type 'void(PriorityQueue *, void *)'
  140 | void pqueue_push(PriorityQueue *pqueue, void *elem) {
      |      ^~~~~~~~~~~
main.c:390:7: error: conflicting types for 'pqueue_pop'; have 'void *(PriorityQueue *)'
  390 | void *pqueue_pop(PriorityQueue *pqueue) { return heap_pop(pqueue->heap); }
      |       ^~~~~~~~~~
main.c:144:7: note: previous definition of 'pqueue_pop' with type 'void *(PriorityQueue *)'
  144 | void *pqueue_pop(PriorityQueue *pqueue) { return heap_pop(pqueue->heap); }
      |       ^~~~~~~~~~
main.c:392:6: error: conflicting types for 'pqueue_empty'; have '_Bool(PriorityQueue *)'
  392 | bool pqueue_empty(PriorityQueue *pqueue) { return heap_empty(pqueue->heap); }
      |      ^~~~~~~~~~~~
main.c:146:6: note: previous definition of 'pqueue_empty' with type '_Bool(PriorityQueue *)'
  146 | bool pqueue_empty(PriorityQueue *pqueue) { return heap_empty(pqueue->heap); }
      |      ^~~~~~~~~~~~
main.c:394:11: error: redefinition of 'INF'
  394 | const int INF = 1 << 30;
      |           ^~~
main.c:148:11: note: previous definition of 'INF' with type 'int'
  148 | const int INF = 1 << 30;
      |           ^~~
main.c:399:3: error: conflicting types for 'Edge'; have 'struct <anonymous>'
  399 | } Edge;
      |   ^~~~
main.c:153:3: note: previous declaration of 'Edge' with type 'Edge'
  153 | } Edge;
      |   ^~~~
main.c:401:7: error: conflicting types for 'new_Edge'; have 'Edge *(int,  int)'
  401 | Edge *new_Edge(int dst, int cost) {
      |       ^~~~~~~~
main.c:155:7: note: previous definition of 'new_Edge' with type 'Edge *(int,  int)'
  155 | Edge *new_Edge(int dst, int cost) {
      |       ^~~~~~~~
main.c:408:12: error: redefinition of 'cmp_Edge'
  408 | static int cmp_Edge(void *lhs, void *rhs) {
      |            ^~~~~~~~
main.c:162:12: note: previous definition of 'cmp_Edge' with type 'int(void *, void *)'
  162 | static int cmp_Edge(void *lhs, void *rhs) {
      |            ^~~~~~~~
main.c:422:9: error: conflicting types for 'dijkstra'; have 'Vector *(Vector *, int)'
  422 | Vector *dijkstra(Vector *tree, int src) {
      |         ^~~~~~~~
main.c:176:9: note: previous definition of 'dijkstra' with type 'Vector *(Vector *, int)'
  176 | Vector *dijkstra(Vector *tree, int src) {
      |         ^~~~~~~~
main.c:457:5: error: redefinition of 'main'
  457 | int main(void) {
      |     ^~~~
main.c:211:5: note: previous definition of 'main' with type 'int(void)'
  211 | int main(void) {
      |     ^~~~