結果

問題 No.807 umg tours
コンテスト
ユーザー akakimidori
提出日時 2019-03-23 11:18:38
言語 C
(gcc 13.3.0)
結果
AC  
実行時間 397 ms / 4,000 ms
コード長 4,764 bytes
コンパイル時間 366 ms
コンパイル使用メモリ 32,512 KB
実行使用メモリ 24,832 KB
最終ジャッジ日時 2024-11-23 19:17:54
合計ジャッジ時間 4,830 ms
ジャッジサーバーID
（参考情報） 		judge5 / judge2
このコードへのチャレンジ
（要ログイン）
ファイルパターン 結果
other AC * 26
権限があれば一括ダウンロードができます

ソースコード

diff # 

#include<stdio.h>
#include<stdlib.h>
#include<stdint.h>
#include<inttypes.h>

typedef struct directed_edge {
  int32_t vertex;
  int32_t cost;
  int32_t next;
} graph_edge;

typedef struct directedGraph {
  graph_edge *edge;
  int32_t *start;
  int32_t pointer;
  int32_t vertex_num;
  int32_t max_size;
} graph;

graph* newGraph (const int vertex_num) {
  graph *g = (graph *) calloc (1, sizeof (graph));
  g->edge = (graph_edge *) calloc (1, sizeof (graph_edge));
  g->start = (int32_t *) calloc (vertex_num, sizeof (int32_t));
  g->pointer = 0;
  g->vertex_num = vertex_num;
  g->max_size = 1;
  for (int32_t i = 0; i < vertex_num; ++i) {
    g->start[i] = -1;
  }
  return g;
}

void addEdge (graph *g, int32_t from, int32_t to, int32_t cost) {
  if (g->pointer == g->max_size) {
    g->max_size *= 2;
    g->edge = (graph_edge *) realloc (g->edge, sizeof (graph_edge) * g->max_size);
  }
  g->edge[g->pointer] = (graph_edge) {to, cost, g->start[from]};
  g->start[from] = g->pointer++;
}

typedef int32_t i32;
typedef int64_t i64;

typedef struct node {
  i32 v;
  i64 d;
} node;

typedef node heap_val;
typedef int32_t heap_index;

const heap_index null_index = -1;

static inline int pairingheap_func_compare (heap_val a, heap_val b) {
  i64 d = a.d - b.d;
  return d == 0 ? 0 : d < 0 ? -1 : 1;
}

typedef struct pairingHeapNode {
  heap_index next;
  heap_index child;
  heap_val val;
} heap_node;

typedef struct pairingHeapHead {
  heap_node *array;
  heap_index root;
  heap_index free_front;
  int32_t heap_size;
  int32_t array_len;
} heap;

void initHeap (heap *h) {
  if (h->array != NULL) {
    free (h->array);
  }
  const int32_t initial_len = 1;
  h->array = (heap_node *) calloc (initial_len, sizeof (heap_node));
  h->array[0].next = null_index;
  h->root = null_index;
  h->free_front = 0;
  h->array_len = initial_len;
  h->heap_size = 0;
}

heap* newHeap (void) {
  heap *h = (heap *) calloc (1, sizeof (heap));
  h->array = NULL;
  initHeap (h);
  return h;
}

int32_t get_heap_size (const heap *h) {
  return h->heap_size;
}

int is_empty (const heap *h) {
  return h->heap_size == 0;
}

static inline heap_index meld (heap_node *array, heap_index a, heap_index b) {
  if (a == null_index) return b;
  if (b == null_index) return a;
  if (pairingheap_func_compare (array[a].val, array[b].val) > 0) {
    heap_index swap = a;
    a = b;
    b = swap;
  } 
  array[b].next = array[a].child;
  array[a].child = b;
  return a;
}

void push (heap *h, const heap_val val) {
  if (h->free_front == null_index) {
    heap_index front = h->array_len;
    h->array_len *= 2;
    h->array = (heap_node *) realloc (h->array, sizeof (heap_node) * h->array_len);
    h->free_front = front;
    for (heap_index i = front; i + 1 < h->array_len; ++i) {
      h->array[i].next = i + 1;
    }
    h->array[h->array_len - 1].next = null_index;
  }
  h->heap_size++;
  const heap_index k = h->free_front;
  h->free_front = h->array[h->free_front].next;
  h->array[k] = (heap_node) {null_index, null_index, val};
  h->root = meld (h->array, h->root, k);
}

heap_val pop (heap *h) {
  h->heap_size--;
  heap_node *array = h->array;
  heap_val res = array[h->root].val;
  array[h->root].next = h->free_front;
  h->free_front = h->root;
  heap_index lst = array[h->root].child;
  heap_index r = null_index;
  while (lst != null_index && array[lst].next != null_index) {
    heap_index a = lst;
    heap_index b = array[a].next;
    lst = array[b].next;
    array[a].next = array[b].next = null_index;
    r = meld (array, r, meld (array, a, b));
  }
  if (lst != null_index) {
    r = meld (array, r, lst);
  }
  h->root = r;
  return res;
}

void run (void) {
  i32 n, m;
  scanf("%" SCNi32 "%" SCNi32, &n, &m);
  graph *g = newGraph (2 * n);
  while (m--) {
    i32 a, b, c;
    scanf("%" SCNi32 "%" SCNi32 "%" SCNi32, &a, &b, &c);
    a--;
    b--;
    addEdge (g, a, b, c);
    addEdge (g, b, a, c);
    addEdge (g, a + n, b + n, c);
    addEdge (g, b + n, a + n, c);
    addEdge (g, a, b + n, 0);
    addEdge (g, b, a + n, 0);
  }
  i64 *dp = (i64 *) calloc (2 * n, sizeof (i64));
  uint8_t *used = (uint8_t *) calloc (2 * n, sizeof (uint8_t));
  for (i32 i = 1; i < n; ++i) {
    dp[i] = (i64) 1000000000 * n;
    dp[i + n] = dp[i];
  }
  heap *h = newHeap ();
  push (h,(node){0, 0});
  while (!is_empty (h)) {
    const node t = pop (h);
    const i32 v = t.v;
    if (used[v]) continue;
    used[v] = 1;
    for (i32 p = g->start[v]; p != -1; p = g->edge[p].next) {
      i32 u = g->edge[p].vertex;
      i64 d = t.d + g->edge[p].cost;
      if (d >= dp[u]) continue;
      dp[u] = d;
      push (h, (node){u, d});
    }
  }
  for (i32 i = 0; i < n; ++i) {
    printf("%" PRIi64 "\n", dp[i] + dp[i + n]);
  }
}

int main (void) {
  run ();
  return 0;
}
0