#include <iostream>
#include <fstream>
#include <cstdlib>
#include <iomanip>
#define INFINITE 99999
using namespace std;

float Graph_Matrix[50][50];
float distance[50];
float A[200];
float B[200];
float C[200][3];
int D[10];
void BuildGraph_Matrix(float *Path_Cost){

int side=D[0];
int Start_Point;
int End_Point;
int i,j;
for(i=1;i<side;i++)
    for(j=1;j<side;j++)
    if(i==j)
     Graph_Matrix[i][j]=0;
     else
        Graph_Matrix[i][j]=INFINITE;

     i=0;
     while(i<side){
       Start_Point=Path_Cost[i*3];
       End_Point=Path_Cost[i*3+1];
       Graph_Matrix[Start_Point][End_Point]=Path_Cost[i*3+2];
       i++;
     }
}



void shortestPath(int vertex1,int vertex_total){
     int side=D[0];
     extern float distance[50];
     int shortest_vertex=1;
     float shortest_distance;
     int goal[side];
     int i,j;
     for(i=1;i<=vertex_total;i++){
        goal[i]=0;
        distance[i]=Graph_Matrix[vertex1][i];
      }
    goal[vertex1]=1;
    distance[vertex1]=0;
    cout<<endl;

    for(i=1;i<=vertex_total-1;i++){
        shortest_distance=INFINITE;
        for(j=1;j<=vertex_total;j++)
            if(goal[j]==0&&shortest_distance>distance[j])
        {
            shortest_distance=distance[j];
            shortest_vertex=j;
        }

        goal[shortest_vertex]=1;
        for(j=1;j<=vertex_total;j++){

           if(goal[j]==0&&distance[shortest_vertex]+Graph_Matrix[shortest_vertex][j]<distance[j])
           {
               distance[j]=distance[shortest_vertex]+Graph_Matrix[shortest_vertex][j];

           }

        }

    }


}

int main(void){

  ifstream ifile;
  ofstream ofile("t2_out.txt");

  ifile.open("test2.txt");

       if(!ifile.is_open()){   //檢查檔案使否有開啟
        return 1;
       }

       int k=0;
       int n=0;
       while(!ifile.eof()){
         ifile >> A[k];
         k++;
       }

     cout<<"number:"<<A[0]<<endl;

       int side;
       side=(k-1)/3;


      cout<<"side="<<side<<endl;
      D[0]=side;

      for(int i=0;i<k;i++){
        B[i]=A[i+1];
      }





     for(int i=0;i<side;i++){
        for(int j=0;j<3;j++){
           C[i][j]=B[i*3+j];

        }


     }


 float Path_Cost[side][3];
  for(int i=0;i<side;i++){
    for(int j=0;j<3;j++){
       Path_Cost[i][j]=C[i][j];
    }
  }


  extern float distance[50];

  int j;
  BuildGraph_Matrix(&Path_Cost[0][0]);


  shortestPath(1,A[0]);
  cout<<"================================"<<endl;
  cout<<"頂點1到各頂點的最短距離:"<<endl;
  cout<<"================================"<<endl;
  for(j=1;j<=A[0];j++)
    cout<<"頂點1到頂點"<<setw(2)<<j<<"的最短距離="<<setw(3)<<distance[j]<<endl;
    cout<<endl;

  for(j=1;j<=A[0];j++)
    ofile<<"頂點1到頂點"<<setw(2)<<j<<"的最短距離="<<setw(3)<<distance[j]<<endl;

   return 0;

}