prim

#include <stdio.h>
#include <math.h>
#include <limits.h>

void showHeapVector(long int* vertexes_pos, long int* costs, long int* parents, long int heap_size){
  //printf("vertex pos: ");
  //for(long int i = 0; i <= heap_size; i++){
  //  printf("%ld ", vertexes_pos[i]);
  //}
  //printf("\n");

  for(long int i = 0; i <= heap_size; i++){
    printf("vertex: %ld - parent: %ld - cost: %ld\n", vertexes_pos[i], parents[vertexes_pos[i]], costs[vertexes_pos[i]]);
  }
  printf("\n");
}

void min_heapify(long int* vertexes_pos, long int* costs, long int index, long int heap_size){
  //printf("enter min_heapify");
  long int left = 2*index + 1;
	long int right = 2*index + 2;
	long int lower;

  if(left <= heap_size && costs[vertexes_pos[left]] < costs[vertexes_pos[index]]){
		lower = left;
	}else{
		lower = index;
	}

	if(right <= heap_size && costs[vertexes_pos[right]] < costs[vertexes_pos[lower]]){
		lower = right;
	}

	if(lower != index){
    long int tmp = vertexes_pos[lower];
    vertexes_pos[lower] = vertexes_pos[index];
    vertexes_pos[index] = tmp;

		min_heapify(vertexes_pos, costs, lower, heap_size);
	}

  //printf("exiting min_heapify!\n");
}

/* returns the vertex with the minimun cost without extract it */
long int heap_minimun(long int* vertexes_pos, long int heap_size){
  if(heap_size < 0) return -1;

  long int vertex = vertexes_pos[0];

  return vertex;
}

long int heap_extract_min(long int* vertexes_pos, long int* costs, long int* parents, long int* heap_size){
  //printf("entering in heap_extract_min ...");
  if(*heap_size < 0) return -1;

  long int min = vertexes_pos[0];
  vertexes_pos[0] = vertexes_pos[*heap_size];

  *heap_size = *heap_size - 1;

  min_heapify(vertexes_pos, costs, 0, *heap_size);

  //printf(" done!\n");
  return min;
}

void heap_decrease_key(long int* vertexes_pos, long int* costs, long int* parents, long int heap_size, long int position, long int key){
  //printf("entering in heap_decrease_key ...");
  //printf("position: %ld\n", position);
  //printf("before:\n");
  //showHeapVector(vertexes_pos, costs, parents, heap_size);
  if(key > costs[vertexes_pos[position]]) return;

  costs[vertexes_pos[position]] = key;

  long int parent_position = (long int)floor((position - 1) / 2);
  //printf("parent pos: %ld\n", parent_position);

  long int new_position = position;
  while((parent_position >= 0) && costs[vertexes_pos[new_position]] < costs[vertexes_pos[parent_position]]){
    //printf("change %ld with %ld\n", vertexes_pos[new_position], vertexes_pos[parent_position]);

    long int tmp = vertexes_pos[new_position];
    vertexes_pos[new_position] = vertexes_pos[parent_position];
    vertexes_pos[parent_position] = tmp;

    new_position = parent_position;

    if(parent_position <= 0) break;

    parent_position = (long int)floor((parent_position - 1) / 2);
    //printf("new parent: %ld \n", parent_position);
  }

  //printf("after:\n");
  //showHeapVector(vertexes_pos, costs, parents, heap_size);
  //printf(" done!\n");
}

void min_heap_insert(long int* vertexes_pos, long int* parents, long int* costs, long int* heap_size, long int vertex, long int cost){
  /* all new vertexs are insert in the end with cost -INF */
  *heap_size = *heap_size + 1;
  vertexes_pos[*heap_size] = vertex;

  if(cost == 0){
    parents[*heap_size] = vertex;
  }else{
    parents[*heap_size] = -1;
  }

  costs[*heap_size] = LONG_MAX;

  heap_decrease_key(vertexes_pos, costs, parents, *heap_size, *heap_size, cost);
}

void prim(long int n, long int graph[n][n], long int source){
  long int vertexes_pos[n], parents[n], costs[n];
  long int heap_size = -1;

  for(long int i = 0; i < n; i++){
    if(i == source){
      min_heap_insert(vertexes_pos, parents, costs, &heap_size, i, 0);
    }else{
      min_heap_insert(vertexes_pos, parents, costs, &heap_size, i, LONG_MAX);
    }

    //printf("insert vertex number %ld\n", i+1);
    //showHeapVector(vertexes_pos, costs, parents, heap_size);
  }

  //showHeapVector(vertexes_pos, costs, parents, heap_size);

  for(long int i = 0; i < n - 1; i++){
    long int min = heap_extract_min(vertexes_pos, costs, parents, &heap_size);

    for(long int j = 0; j <= heap_size; j++){
      //printf("computing cost from %ld to %ld - cost: %ld\n", min, vertexes_pos[j], graph[min][vertexes_pos[j]]);

      if(graph[min][vertexes_pos[j]] > 0 && costs[vertexes_pos[j]] > graph[min][vertexes_pos[j]]){
        //printf("Updating cost from %ld to %ld - old: %ld --> new: %ld\n", min, vertexes_pos[j], costs[vertexes_pos[j]], graph[min][vertexes_pos[j]]);

        heap_decrease_key(vertexes_pos, costs, parents, heap_size, j, graph[min][vertexes_pos[j]]);

        parents[vertexes_pos[j]] = min;
      }
    }

    //showHeapVector(vertexes_pos, costs, parents, heap_size);
    //printf("\n");
  }

  long int total = 0;
  //printf("\n");
  //printf("---- costs ----\n");
  for(long int i = 0; i < n; i++){
  //  printf("vertex: %ld - parent: %ld - cost: %ld\n", i, parents[i], costs[i]);
    total += costs[i];
  }
  printf("%ld\n", total);
}

int main(void) {
  long int n;

  scanf("%ld", &n);

  long int graph[n][n];
  long int weight;

  for(long int i = 0; i < n-1; i++){
    for(long int j = 0; j < n - 1 - i; j++){
      scanf("%ld", &weight);
      graph[i][j+i+1] = weight;
      graph[i+j+1][i] = weight;
    }
    graph[i][i] = 0;
  }
  graph[n-1][n-1] = 0;

  prim(n, graph, 0);
}