提出 #22378051

---

ソースコード 拡げる

#include <stdio.h>

#define INF 1000000001

typedef struct list {
  int op;
  int cost;
  struct list *next;
} list;

list pool[200000] = {};
int used = 0;

void down_heap (int i, int num_elem, int *pri_queue, int *val, int* map) {
  int ch[2] = { INF, INF };

  if (num_elem <= 2*i+1) {
    return;
  }
  
  ch[0] = val[pri_queue[2*i+1]];
  if (num_elem > 2*i+2) {
    ch[1] = val[pri_queue[2*i+2]];
  }
  
  if (ch[0] < ch[1] && ch[0] < val[pri_queue[i]]) {
    int tmp = pri_queue[i];
    pri_queue[i] = pri_queue[2*i+1];
    pri_queue[2*i+1] = tmp;
    map[pri_queue[i]] = i;
    map[pri_queue[2*i+1]] = 2*i+1;
    down_heap (2*i+1, num_elem, pri_queue, val, map);
  } else if (ch[1] < ch[0] && ch[1] < val[pri_queue[i]]) {
    int tmp = pri_queue[i];
    pri_queue[i] = pri_queue[2*i+2];
    pri_queue[2*i+2] = tmp;
    map[pri_queue[i]] = i;
    map[pri_queue[2*i+2]] = 2*i+2;
    down_heap (2*i+2, num_elem, pri_queue, val, map);
  }
  
  return;
}

void up_heap (int i, int *pri_queue, int *val, int *map) {
  int parent = (i - 1) / 2;
  
  if (i == 0) {
    return;
  }
  
  if (val[pri_queue[i]] < val[pri_queue[parent]]) {
    int tmp = pri_queue[i];
    pri_queue[i] = pri_queue[parent];
    pri_queue[parent] = tmp;
    map[pri_queue[i]] = i;
    map[pri_queue[parent]] = parent;
    up_heap (parent, pri_queue, val, map);
  } 
  
  return;
}

int dequeue(int *num_elem, int *pri_queue, int *val, int* map) {
  int ans = pri_queue[0];
  
  *num_elem -= 1;
  pri_queue[0] = pri_queue[*num_elem];
  map[pri_queue[0]] = 0;
  
  down_heap(0, *num_elem, pri_queue, val, map);
  
  return ans;
}

void dijkstra(int *num_elem, int *pri_queue, int *d, int* map, list **e) {
  while (*num_elem > 0) {
    int v = dequeue(num_elem, pri_queue, d, map);
    list *l = e[v];
    
    while (l != NULL) {
      int tmp_d = d[v] + l->cost;
      if (tmp_d < d[l->op-1]) {
            
        if (pri_queue[map[l->op-1]] != l->op-1) {
          while (1) {
            int a = 0;
            a++;
          }
        }
        d[l->op-1] = tmp_d;
        up_heap(map[l->op-1], pri_queue, d, map);
      }
      l = l->next;
    }
  }
  
  return;
}

int main () {
  int n = 0;
  int m = 0;
  
  int res = 0;
  
  list *e[100000] = {};
  
  int d1[100000] = {};
  int dn[100000] = {};
  int pri_queue[100000] = {};
  int num_elem = 0;
  int map[100000] = {};
  int visited[100000] = {};
  
  res = scanf("%d", &n);
  res = scanf("%d", &m);
  
  for (int i = 0; i < m; i++) {
    int a = 0;
    int b = 0;
    int c = 0;
    
    res = scanf("%d", &a);
    res = scanf("%d", &b);
    res = scanf("%d", &c);
    
    pool[used].op = b;
    pool[used].cost = c;
    pool[used].next = e[a-1];
    e[a-1] = pool+used;
    used++;
    
    pool[used].op = a;
    pool[used].cost = c;
    pool[used].next = e[b-1];
    e[b-1] = pool+used;
    used++;
  }
  
  for (int i = 0; i < n; i++) {
    d1[i] = INF;
    dn[i] = INF;
    pri_queue[num_elem] = i;
    map[i] = num_elem;
    num_elem++;
  }
  
  d1[0] = 0;
  dn[n-1] = 0;
  
  dijkstra(&num_elem, pri_queue, d1, map, e);
  
  pri_queue[0] = n-1;
  map[n-1] = 0;
  num_elem = 1;
  for (int i = 0; i < n - 1; i++) {
    pri_queue[num_elem] = i;
    map[i] = num_elem;
    num_elem++;
  }
  
  dijkstra(&num_elem, pri_queue, dn, map, e);
  
  for (int i = 0; i < n; i++) {
    printf("%d\n", d1[i]+dn[i]);
  }
  
  return 0;
}

提出情報

ジャッジ結果