#include<iostream>
#define INFINITY 10000//最大数 
using namespace std;
const int maxEdges=50; 
const int maxVertices=100; //最大顶点数 

struct PathWay{
    double dist;//权值
};

class MyGraph
{
    private:
        int vNum;//当前顶点数
        int eNum;//当前边数
        char Vertex[maxVertices];//顶点数组
        PathWay Edge[maxVertices][maxVertices];//边数组
        
    public:
        void Create(int size = maxEdges);//构造函数
        bool FindVertex(int vertex);
        bool InsertVertex(int vertex);//插入一个顶点vertex
        bool InsertEdge(const int v1,const int v2,const int weight);//插入一条边(v1,v2),该边上的权值为weight
        bool GetVertexPos(const int &vertex,int &i);//给出顶点vertex在图中的位置
        void Floyd();//Floyd算法 
        void Print();//输出邻接矩阵 
        void short_compare(double farthest[]);//求出最短路径 
        double far_compare(double shortest[]);//这个问题的答案，在short_compare函数中选出一个最小的值 

}; 

void MyGraph::Create(int size)//将图转化成邻接矩阵保存 
{ 
    int n,e;//n是村庄数，e是边数 
    char name,tail,head;
    int weight;
    for(int i=0;i<size;i++){
        for(int j=0;j<size;j++)
        {
            if(i==j){
                Edge[i][j].dist=0;//初始化顶点到自身权值为0
            }    
            else{
                Edge[i][j].dist=INFINITY;//初始化邻接矩阵其余顶点为最大值
            }   
        }
    }
    
    cout<<"请输入总顶点数（村庄）：";
    cin>>n;
    while(cin.fail()){  
        cin.clear();  
        char temp[100];  
        cin.getline(temp,100);  
        cout<<endl;  
        cout<<"Error:您输入的不是数字."<<endl<<"请重新输入:";  
        cin>>n;  
        cout<<endl;  
    } 
    
    cout<<"请输入总边数（路径）:";
    cin>>e;
    while(cin.fail()){  
        cin.clear();  
        char temp[100];  
        cin.getline(temp,100);  
        cout<<endl;  
        cout<<"Error:您输入的不是数字."<<endl<<"请重新输入:";  
        cin>>e;  
        cout<<endl;  
    } 
    cout<<endl;
    
    cout<<"请输入顶点名称:"<<endl;
    for(int i=0;i<n;i++)//依次输入顶点，插入图中
    {
        cout<<"请输入第"<<i+1<<"个顶点（村庄）的名称：";
        cin>>name;
        InsertVertex(name);
        vNum++;
    }
       cout<<endl; 
 
    cout<<"请输入头尾两个顶点（村庄）和权值（路径）[分别用空格隔开]："<<endl;
    for(int i=0;i<e;i++){
       
        cin>>head>>tail>>weight;
        if(!InsertEdge(head,tail,weight))
        {
            cout<<"不存在该边，请重新输入这条边：";
            i--; 
            continue;          
        }
    }
    cout<<endl; 
}

void MyGraph::short_compare(double farthest[]){
//比较数组（当前村庄和其他村庄间最短距离的集合中最大值的集合）中的最小值。选择使离医院最远的村庄到医院的路程最短  
    double route=farthest[0];  
    int point=0;  
    for (int i=0; i<vNum; i++) {  
        if (farthest[i]<route) {  
            route=farthest[i];  
            point=i;  
        }  
    }  
    cout<<"所以医院应该建在村庄："<<Vertex[point]<<endl;  
}  

double MyGraph::far_compare(double s[]){//得到最远村庄的距离
    double max=s[0];
    int k;
    for(k=0;k<vNum;k++){
        if(s[k]>max){
            max=s[k];            
        }
    }
    return max;
} 
 
bool MyGraph::FindVertex(int vertex)//给出顶点vertex在图中的位置，这里也可以用来判断在插入的时候是否已经有顶点了 
{
    for (int i = 0; i < vNum; i++){ 
        if (vertex == Vertex[i]){ 
            return true;
        } 
    } 
    return false;
} 
bool MyGraph::InsertVertex(int vertex)//插入顶点
{
    if (FindVertex(vertex)){ 
        return false;
    } 
    else{    
        Vertex[vNum] = vertex;
        return true;
    } 
} 
bool MyGraph::GetVertexPos(const int& vertex,int &i)//这个点是否在这条边上 
{
    for (i = 0; i < vNum; i++){ 
        if (vertex == Vertex[i]){ 
            return true;
        } 
    } 
    return false;
} 
bool MyGraph::InsertEdge(int v1,int v2,int weight)//插入一条边
{ 
    int k=0,j=0;
    
    if(GetVertexPos(v1,k) && GetVertexPos(v2,j))
    {
        Edge[k][j].dist=weight;
        eNum++;
        Edge[j][k].dist=weight;
        eNum++;
        return true;
    }
    else{
        return false; 
    }   
} 

void MyGraph::Floyd() 
{
    double map[maxVertices][maxVertices],shortDistance[maxVertices],longDistance[maxVertices];//longDistance就是我们问题的答案 
//map存放其他村庄到当前村庄的路径和，shortDistance当前村庄到最远村庄的最短距离，longDistance是shortDistance中的最大距离  
    int current,start,mid,i,j,k;
    j=k=0;
    for (current=0; current<vNum; current++){
        for (start=0; start<vNum; start++) {
            map[current][start] = Edge[current][start].dist;
        }
    }//各对结点之间初始已知路径及距离
                                   
    for (mid=0; mid<vNum; mid++){
        if(vNum-1 == mid){
//这里看插入的点是否等于顶点数减一，如果小于的话证明还没插完整，加上前面的继续插，不可能大于，然后插到倒数第一个，比方说
//我们这个题有6个点，则插五个点就够了，排除自己的。然后当插到第五个点的时候我们就可以判断第五个点插进去是否小于之前的，然后输出他的距离。 
            for(current=0; current<vNum; current++){
                k=0;
                shortDistance[k]=0;
                for (start=0; start<vNum; start++){
                    if (map[current][mid] + map[mid][start] < map[current][start]){
                        map[current][start] = map[current][mid] + map[mid][start];
                    }
                    if(current != start){//这里要杜绝自己到自己的路径 
                        cout<<"村庄"<<Vertex[current]<<"到村庄"<<Vertex[start]<<"的最短距离为："<<map[current][start]<<endl;
                        shortDistance[k] = map[current][start];
                        k++;
                    }
                }
                longDistance[j] = far_compare(shortDistance);
                cout<<"村庄"<<Vertex[current]<<"到最远的村庄的最短距离为:"<<longDistance[j]<<endl;
                j++;
                cout<<endl;
            }    
        }else{//没有插完整的话继续插 
            for (current=0; current<vNum; current++){
                for (start=0; start<vNum; start++){
                    if (map[current][mid] + map[mid][start] < map[current][start]){
                        map[current][start] = map[current][mid] + map[mid][start]; 
                    }
                }    
            }
        }
    }
    short_compare(longDistance);
}

void MyGraph::Print(){
    int i,j,count=0;
    cout<<"所得图的邻接矩阵为："<<endl;
    for(i=0;i<vNum;i++){
           for(j=0;j<vNum;j++){
               if(Edge[i][j].dist!=INFINITY){ 
                   cout<<Edge[i][j].dist<<"\t";
               } 
               else if(i==j){
                   cout<<0<<"\t";
            } 
               else{ 
                   cout<<"∞"<<"\t";
               } 
               
               count++;
        }
        
        if(count%vNum==0){ 
                cout<<endl;
        }
             
    }
    cout<<endl;
}

int main() 
{ 
    MyGraph Hospital;
    Hospital.Create(maxVertices);
    Hospital.Print();
     Hospital.Floyd();
    return 0;
}