dijkstra

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

long int extract_min(long int* dist, long int* visited, long int size){
  long int min_value = LONG_MAX, min_index;
  for(long int i = 0; i < size; i++){
    if(visited[i] == 0 && dist[i] < min_value){
      min_index = i;
      min_value = dist[i];
    }
  }
  return min_index;
}

void dijkstra(long int n, long int graph
[n][n], long int source, long int destiny){
  // initialize single source
  long int dist[n], visited[n], predecessor[n];
  for(long int i = 0; i < n; i++){
    dist[i]= LONG_MAX;
    visited[i] = 0;
  }

  predecessor[source] = -1;
  dist[source] = 0;

  for(long int i = 0; i < n - 1; i++){
    long int u = extract_min(dist, visited, n);
    visited[u] = 1;

    for(long int j = 0; j < n; j++){
      if(visited[j] == 0 && graph[u][j] != 0 && dist[j] > dist[u] + graph[u][j]){
        dist[j] = dist[u] + graph[u][j];
        predecessor[j] = u;
      }
    }
  }

  printf("%ld\n", dist[destiny]);

  // Show path
  //long int v = predecessor[destiny];
  //printf("%ld", destiny);
  //while(v != -1){
  //  printf(" %ld", v);
  //  v = predecessor[v];
  //}
  //printf("\n");
}

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;

  dijkstra(n, graph, 0, n - 1);

  return 0;
}