#include <stdio.h>
#include <malloc.h>
#include <stdbool.h>
#define VertexNum 100
#define INFINITY 65535
typedef int Vertex;
struct ENode{
Vertex V1,V2;
int Weight;
};
typedef struct ENode *PtrToENode;
typedef PtrToENode Edge;
struct GNode{
int Nv;
int Ne;
int G[VertexNum][VertexNum];
};
typedef struct GNode *PtrToGNode;
typedef PtrToGNode MGraph;
MGraph CreateGraph(int VertexNums);
void InsertEdge(MGraph Graph,Edge E);
MGraph BuildGraph();
void FindAnimal(MGraph G);
int FindMaxDist(int D[][VertexNum],Vertex i,int N);
bool Floyd(MGraph Graph,int D[][VertexNum],Vertex path[][VertexNum]);
bool Floyd(MGraph Graph,int D[][VertexNum],Vertex path[][VertexNum]){
Vertex i,j,k;
for(i = 0;i < Graph->Nv;i++){
for(j = 0;j < Graph->Nv;j++){
D[i][j] = Graph->G[i][j];
path[i][j] = -1;
}
}
for(k = 0;k < Graph->Nv;k++){
for(i = 0;i < Graph->Nv;i++){
for(j = 0;j < Graph->Nv;j++){
if(D[i][k] + D[k][j] < D[i][j]){
D[i][j] = D[i][k] + D[k][j];
if(i == j && D[i][j] < 0){
return false;
}
}
path[i][j] = k;
}
}
}
return true;
}
int FindMaxDist(int D[][VertexNum],Vertex i,int N){
int MaxDist;
Vertex j;
MaxDist = 0;
for(j = 0;j < N;j++){
if(i != j && D[i][j] > MaxDist){
MaxDist = D[i][j];
}
}
return MaxDist;
}
void FindAnimal(MGraph Graph){
int D[VertexNum][VertexNum],path[VertexNum][VertexNum],MaxDist,MinDist;
Vertex Animal,i;
bool result = Floyd(Graph,D,path);
if(result){
MinDist = INFINITY;
for(i = 0;i < Graph->Nv;i++){
MaxDist = FindMaxDist(D,i,Graph->Nv);
if(MaxDist == INFINITY){
printf("0\n");
return;
}
if(MinDist > MaxDist){
MinDist = MaxDist;
Animal = i + 1;
}
}
}
printf("最容易变的动物是:%d号,变为最难变的距离需:%d\n",Animal,MinDist);
}
MGraph BuildGraph(){
MGraph Graph;
Edge E;
int Nv;
printf("输入结点数:\n");
scanf("%d",&Nv);
Graph = CreateGraph(Nv);
printf("输入边数:\n");
scanf("%d",&Graph->Ne);
if(Graph->Ne != 0){
E = (Edge)malloc(sizeof(struct ENode));
for(int i = 0;i < Graph->Ne;i++){
printf("输入要插入边的两个顶点以及权重\n");
scanf("%d %d %d",&E->V1,&E->V2,&E->Weight);
E->V1--;
E->V2--;
InsertEdge(Graph,E);
}
}
return Graph;
}
void InsertEdge(MGraph Graph,Edge E){
Graph->G[E->V1][E->V2] = E->Weight;
Graph->G[E->V2][E->V1] = E->Weight;
}
MGraph CreateGraph(int VertexNums){
MGraph Graph = (MGraph)malloc(sizeof(struct GNode));
Graph->Nv = VertexNums;
Graph->Ne = 0;
for(int i = 0;i < Graph->Nv;i++){
for(int j = 0;j < Graph->Nv;j++){
Graph->G[i][j] = INFINITY;
}
}
return Graph;
}
int main () {
MGraph G = BuildGraph();
FindAnimal(G);
return 0;
}