#include <stdio.h>
#include <stdlib.h>
#include <assert.h>

#define N 14 /* 頂点の数*/
#define START 0 /* 始点の頂点番号*/
#define END 6 /* 終点の頂点番号*/
int g[N][N] = { /* グラフG はN 行N 列の配列*/
/* 0 1 2 3 4 5 6 7 8 9 10 11 12 13 */
{ 0, 1, 0, 0, 0, 0, 0, 0, 0, 0, 3, 0, 0, 0},
{ -1, 0, 2, 0, 0, 0, 0, 0, 0, 0, 0, 1, 0, 0},
{ 0, -2, 0, 5, 0, 0, 0, 0, 0, 0, 0, 0, 4, 0},
{ 0, 0, -5, 0, 8, 0, 0, 0, 0, 0, 0, 0, -8, -1},
{ 0, 0, 0, -8, 0, 2, 0, 0, 0, 0, 0, 0, 0, 0},
{ 0, 0, 0, 0, -2, 0, 1, 0, -6, 0, 0, 0, -2, 0},
{ 0, 0, 0, 0, 0, -1, 0, -2, 0, 0, 0, 0, 0, 0},
{ 0, 0, 0, 0, 0, 0, 2, 0, -1, 0, 0, 0, 0, 0},
{ 0, 0, 0, 0, 0, 6, 0, 1, 0, -5, 0, 0, 0, -3},
{ 0, 0, 0, 0, 0, 0, 0, 0, 5, 0, -2, -3, 7, 1},
{ -3, 0, 0, 0, 0, 0, 0, 0, 0, 2, 0, 6, 0, 0},
{ 0, -1, 0, 0, 0, 0, 0, 0, 0, 3, -6, 0, 5, 0},
{ 0, 0, -4, 8, 0, 2, 0, 0, 0, -7, 0, -5, 0, 1},
{ 0, 0, 0, 1, 0, 0, 0, 0, 3, -1, 0, 0, -1, 0}
};
#define INIT 0

struct route {
  int nodenum;
  struct route *next;
};

void add_list(struct route **node, int p) {
  struct route *n;
  assert(node != NULL);
  if ((n = malloc(sizeof(struct route))) != NULL) {
    n->nodenum = p;
    n->next = *node;
    *node = n;
  }
}

void clear_list(struct route **node) {
  if (*node == NULL)
    return;
  if ((*node)->next != NULL)
    clear_list(&((*node)->next));
  free(*node);
  *node = NULL;
}

void print_list(struct route *node) {
  if (node != NULL) {
    printf("<%d>, ", node->nodenum);
    print_list(node->next);
  }
}

struct nodedata {
  int tocheck;
  int dist;
  struct route *list;
} nodedata[N];

int main() {
  struct route *rvs, *p;
  int point, t, i, flag;
  for (i = 0; i < N; i++) {
    nodedata[i].tocheck = 0;
    nodedata[i].dist = INIT;
    nodedata[i].list = NULL;
  }
  nodedata[START].tocheck = 1;
  nodedata[START].dist = 0;
  do {
    flag = 0;
    for (point = 0; point < N; point++) {
      if (nodedata[point].tocheck > 0) {
        for (i = 0; i < N; i++) {
          if (g[point][i] > 0) {
            if ((t = nodedata[point].dist + g[point][i]) > nodedata[i].dist) {
              clear_list(&(nodedata[i].list));
              nodedata[i].dist = t;
              add_list(&(nodedata[i].list), point);
              nodedata[i].tocheck = 1;
              flag = 1;
            } else if (t == nodedata[i].dist) {
              add_list(&(nodedata[i].list), point);
              flag = 1; /* need or not need? */
            }
          }
        }
        nodedata[point].tocheck = 0;
      }
    }
  } while (flag > 0);
/*
  for (i = 0; i < N; i++) {
    printf("node %d: dist = %d: ", i, nodedata[i].dist);
    print_list(nodedata[i].list);
    putchar('\n');
  }
*/
  rvs = NULL;
  for (i = END; i != START; i = (nodedata[i].list)->nodenum)
    add_list(&rvs, i);
  printf("V0");
  for (p = rvs; p != NULL; p = p->next)
    printf(" --> V%d", p->nodenum);
  putchar('\n');
  printf("sum of weight: %d\n", nodedata[END].dist);
  clear_list(&rvs);
  for (i = 0; i < N; i++)
    clear_list(&(nodedata[i].list));
  return 0;
}
/* end */

V0 --> V10 --> V11 --> V9 --> V12 --> V3 --> V4 --> V5 --> V6
sum of weight: 38