/*
   Thuat giai A*
   Programming by Edward_Thien
*/

//Include Header Files
#include <iostream>
#include <conio.h>
#include <stdio.h>
#include <iomanip>

//Using namespcase
using namespace std;

//Define consts
const int MAX = 100;

//Declare Data struct
typedef struct DINH
{
   int name;      //Ten
   int f;         //Chi phi g(s) + h(s)
   int g;         //Chi phi tu S --> dinh do
   int prev;      //Luu dinh truoc no
};

typedef struct ARRAY
{
   int n;
   int data[MAX];
};

typedef struct ARRAYDINH
{
   int n;
   DINH data[MAX];
};

typedef struct MATRIX
{
   int n;
   int data[MAX][MAX];
};

//Global variable
int n;            //So dinh
MATRIX DT;         //Do thi khoang cach
ARRAY H;         //Mang chua H
ARRAYDINH O;      //Tap Open
ARRAYDINH C;      //Tap Close

//Prototype
void ReadFile();                              //Doc file
void OutMatrix(MATRIX A);                        //Xuat Matrix
void OutArray(ARRAY A);                           //Xuat Array
void Init();                                 //Khoi tao
int FindMin();                                 //Tim min
void AddToList(DINH n, ARRAYDINH &A);               //Them 1 dinh vao danh sach
void RemoveFromList(int index, ARRAYDINH &A);         //Xoa 1 dinh khoi danh sach
int IsInList(int name, ARRAYDINH A);               //Kiem tra xem dinh do co trong danh sach hay ko?
void Process(int begin);                        //Ham xu ly chinh
void OutResult(int begin);                              //Xuat ket qua

//Main function
int main()
{
   ReadFile();
   OutMatrix(DT);
   cout<<endl;
   OutArray(H);
   cout<<endl;
   Init();
   Process(0);
   OutResult(0);
   _getch();
   return 0;
}

//Define functions
void ReadFile()
{
   FILE *f;
   f = fopen("C:\\Asao.txt", "r");
   if(f == NULL)
   {
      cout<<"Loi mo file";
      return;
   }

   fscanf(f, "%d", &DT.n);
   for(int i = 0; i < DT.n; i++)
   {
      for(int j = 0; j < DT.n; j++)
      {
         fscanf(f, "%d", &DT.data[i][j]);
      }
   }
   H.n = DT.n;
   for(int k = 0; k < H.n; k++)
   {
      fscanf(f, "%d", &H.data[k]);
   }
   fclose(f);
}

void OutMatrix(MATRIX DT)
{
   cout<<DT.n<<endl;
   for(int i = 0; i < DT.n; i++)
   {
      for(int j = 0; j < DT.n; j++)
      {
         if(DT.data[i][j] == 32000)
         {
            cout<<setw(5)<<"--";
         }
         else
         {
            cout<<setw(5)<<DT.data[i][j];
         }
      }
      cout<<endl;
   }
}

void OutArray(ARRAY H)
{
   for(int k = 0; k < H.n; k++)
   {
      cout<<setw(5)<<H.data[k];
   }
}

void Init()
{
   O.n = C.n = 0;
}

int FindMin()
{
   int min = 0;
   for(int i = 1; i < O.n; i++)
   {
      if(O.data[i].f < O.data[min].f)
      {
         min = i;
      }
   }
   return min;
}

void AddToList(DINH n, ARRAYDINH &A)
{
   A.data[A.n++] = n;
}

void RemoveFromList(int index, ARRAYDINH &A)
{
   A.data[index] = A.data[A.n-- - 1];
}

int IsInList(int name, ARRAYDINH A)
{
   for(int i = 0; i < A.n; i++)
   {
      if(A.data[i].name == name)
      {
         return i;
      }
   }
   return -1;
}

void Process(int begin)
{
   DINH S;
   S.name = begin;
   S.g = 0;
   S.f = H.data[begin];
   AddToList(S, O);

   DINH N = S;
   int vitrimin = 0;
   while(S.name != 8)
   {
      int vitri = FindMin();
      S = O.data[vitri];
      for(int i = 0; i < DT.n; i++)
      {
         //Mo cac Q ke voi N, Q khong thuoc C
         if(DT.data[S.name][i] > 0 && IsInList(i, C) == -1)
         {
            vitri = IsInList(i, O);
            //Q thuoc O
            if(vitri >= 0)
            {
               if(S.g + DT.data[S.name][i] < O.data[vitri].g)
               {
                  O.data[vitri].g = S.g + DT.data[S.name][i];
                  O.data[vitri].f = O.data[vitri].g + H.data[i];
                  O.data[vitri].prev = S.name;
               }
            }
            //Q khong thuoc O
            else
            {
               DINH Q;
               Q.name = i;
               Q.g = S.g + DT.data[S.name][i];
               Q.f = Q.g + H.data[i];
               Q.prev = S.name;
               AddToList(Q, O);
            }
         }
      }//Het for
      AddToList(S, C);
      RemoveFromList(vitrimin, O);
      vitrimin = FindMin();
      S = O.data[vitrimin];
   }//Het while
   AddToList(S, C);
}

void OutResult(int begin)
{
   int ten = 8;
   int v = IsInList(ten, C);
   int sum = 0;
   cout<<"\nDuong di la: ";
   cout<<ten;
   while(ten != begin)
   {
      int vitri = IsInList(ten, C);
      ten = C.data[vitri].prev;
      cout<<" <- "<<ten;
   }
   cout<<"\nDo dai duong di: "<<C.data[v].g;
}



/*
   END
*/

9
0 5 4 3 0 0 0 0 0
5 0 3 0 7 8 0 0 0
4 3 0 0 0 2 0 0 0
3 0 0 0 0 4 4 0 0
0 7 0 0 0 1 0 0 6
0 8 2 4 1 0 0 0 0
0 0 0 4 0 0 0 7 0
0 0 0 0 0 0 7 0 3
0 0 0 6 0 0 0 3 0
10 8 7 9 5 4 7 1 0