//c++的程序
#include<iostream.h>
#include<stdlib.h>
template<class T>
class Graph
{
  public:
    Graph(int vertices=10)
    {
      n=vertices;
      e=0;
    }
    ~Graph(){}
    virtual bool Add(int u,int v,const T& w)=0;
    virtual bool Delete(int u,int v)=0;
    virtual bool Exist(int u,int v)const=0;
    int Vertices()const{return n;}
    int Edges()const{return e;}
  protected:
    int n;
    int e;
};
template<class T>
class MGraph:public Graph<T>
{
  public:
    MGraph(int Vertices=10,T noEdge=0);
    ~MGraph();
    bool Add(int u,int v,const T& w);
    bool Delete(int u,int v);
    bool Exist(int u,int v)const;
    void Floyd(T**& d,int**& path);
    void print(int Vertices);
  private:
    T NoEdge;
    T** a;
};
template<class T>
MGraph<T>::MGraph(int Vertices,T noEdge)
{
  n=Vertices;
  NoEdge=noEdge;
  a=new T* [n];
  for(int i=0;i<n;i++){
    a[i]=new T[n];
    a[i][i]=0;
    for(int j=0;j<n;j++)if(i!=j)a[i][j]=NoEdge;
  }
}
template<class T>
MGraph<T>::~MGraph()
{
  for(int i=0;i<n;i++)delete[]a[i];
  delete[]a;
}
template<class T>
bool MGraph<T>::Exist(int u,int v)const
{
  if(u<0||v<0||u>n-1||v>n-1||u==v||a[u][v]==NoEdge)return false;
  return true;
}
template<class T>
bool MGraph<T>::Add(int u,int v,const T& w)
{
  if(u<0||v<0||u>n-1||v>n-1||u==v||a[u][v]!=NoEdge){
    cerr<<"BadInput!"<<endl;
    return false;
  }
  a[u][v]=w;
  e++;
  return true;
}
template<class T>
bool MGraph<T>:delete(int u,int v)
{
  if(u<0||v<0||u>n-1||v>n-1||u==v||a[u][v]==NoEdge){
    cerr<<"BadInput!"<<endl;
    return false;
  }
  a[u][v]=NoEdge;
  e--;
  return true;
}
template<class T>
void MGraph<T>::Floyd(T**& d,int**& path)
{
  d=new T* [n];
  path=new int* [n];
  for(int i=0;i<n;i++){
    d[i]=new T[n];
    path[i]=new int[n];
    for(int j=0;j<n;j++){
      d[i][j]=a[i][j];
      if(i!=j&&a[i][j]<NoEdge)path[i][j]=i;
      else path[i][j]=-1;
    }
  }
  for(int k=0;k<n;k++){
    for(i=0;i<n;i++)
      for(int j=0;j<n;j++)
        if(d[i][k]+d[k][j]<d[i][j]){
          d[i][j]=d[i][k]+d[k][j];
          path[i][j]=path[k][j];
        }
        }
}
template<class T>
void MGraph<T>::print(int Vertices)
{
  for(int i=0;i<Vertices;i++)
    for(int j=0;j<Vertices;j++)
    {
      
      cout<<a[i][j]<<' ';if(j==Vertices-1)cout<<endl;
    }
}
#define noEdge 10000
#include<iostream.h>
void main()
{
  cout<<"請輸入該圖的節點數："<<endl;
  int vertices;
  cin>>vertices;
  MGraph<float> b(vertices,noEdge);
  cout<<"請輸入u,v,w:"<<endl;
  int u,v;
  float w;
  cin>>u>>v>>w;
  while(w!=noEdge){
    //u=u-1;
    b.Add(u-1,v-1,w);
    b.Add(v-1,u-1,w);
    cout<<"請輸入u,v,w:"<<endl;
    cin>>u>>v>>w;
  }
  b.print(vertices);
  int** Path;
  int**& path=Path;
  float** D;
  float**& d=D;
  b.Floyd(d,path);
  for(int i=0;i<vertices;i++){
    for(int j=0;j<vertices;j++){
      cout<<Path[i][j]<<' ';
      if(j==vertices-1)cout<<endl;
    }
  }
  int *V;
  V=new int[vertices+1];
  cout<<"請輸入任意一個初始H-圈："<<endl;
  for(int n=0;n<=vertices;n++){
    
    cin>>V[n];
  }
  for(n=0;n<55;n++){
    for(i=0;i<n-1;i++){
    for(int j=0;j<n-1;j++)
    {
      if(i+1>0&&j>i+1&&j<n-1){
        if(D[V[i]][V[j]]+D[V[i+1]][V[j+1]]<D[V[i]][V[i+1]]+D[V[j]][V[j+1]]){
          int l;
          l=V[i+1];V[i+1]=V[j];V[j]=l;
        }
      }
    }
  }
  }
  float total=0;
  cout<<"最小回路："<<endl;
  for(i=0;i<=vertices;i++){
    
    cout<<V[i]+1<<' ';
  }
  cout<<endl;
  for(i=0;i<vertices;i++)
  total+=D[V[i]][V[i+1]];
  cout<<"最短路徑長度："<<endl;
  cout<<total;
}