中国大学MOOC-陳越、何欽銘-データ構造-2018秋07-図4ハリー・ポッターの試験(25点)

#include 

using namespace std;

#define MaxVertexNum 100 /*       100*/
#define INFINITY 65535	/*                 */ 

typedef int Vertex; /*       ，      */ 
typedef int WeightType; /*        */

/*      */ 
typedef struct ENode{
	Vertex V1, V2;
	WeightType Weight;
}ENode; 
typedef ENode *PtrToENode; 
typedef PtrToENode Edge;

/*      */
typedef struct GNode{
	int NumberofVertex;
	int NumberofEdge;
	WeightType G[MaxVertexNum][MaxVertexNum];
}GNode; 
typedef GNode *PtrToGNode;
typedef PtrToGNode MGraph;

MGraph CreateGraph(int VertexNum);
void InsertEdge(MGraph Graph, Edge E);
MGraph BuildGraph();
void Floyd(MGraph Graph, WeightType Dist[][MaxVertexNum]);
void FindAnimal(MGraph Graph);
WeightType FindMaxDist(WeightType Dist[][MaxVertexNum], Vertex i, int N);

int main()
{
	#ifdef ONLINE_JUDGE
	#else
	freopen("in.txt", "r", stdin);
	#endif
	
	MGraph G = BuildGraph();
	
	FindAnimal(G);
	
	return 0;
}
/*      VertexNum          */
MGraph CreateGraph(int VertexNum)
{
	Vertex V, W;
	MGraph Graph;
	 
	Graph = new GNode;
	Graph->NumberofVertex = VertexNum;
	Graph->NumberofEdge = 0;
	
	for(V = 0; V < Graph->NumberofVertex; V++){
		for(W = 0; W < Graph->NumberofVertex; W++){
			Graph->G[V][W] = INFINITY;
		}
	}
	
	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 BuildGraph()
{
	MGraph Graph;
	Edge E;
	int NumberofVertex;
	
	cin >> NumberofVertex;
	Graph = CreateGraph(NumberofVertex);
	cin >> Graph->NumberofEdge;
	
	if(Graph->NumberofEdge != 0){
		E = new ENode;
		
		for(int i = 0; i < Graph->NumberofEdge; i++){
			cin >> E->V1 >> E->V2 >> E->Weight;
			E->V1--;
			E->V2--;
			InsertEdge(Graph, E);
			
		}
	}
	
	return Graph;
} 

/*     Floyd  */
void Floyd(MGraph Graph, WeightType Dist[][MaxVertexNum])
{
	Vertex i, j, k;
	
	for(i = 0; i < Graph->NumberofVertex; i++){
		for(j = 0; j < Graph->NumberofVertex; j++){
			Dist[i][j] = Graph->G[i][j];
		}
	}
	
	for(k = 0; k < Graph->NumberofVertex; k++){
		for(i = 0; i < Graph->NumberofVertex; i++){
			for(j = 0; j < Graph->NumberofVertex; j++){
				if(Dist[i][k] + Dist[k][j] < Dist[i][j]){
					Dist[i][j] = Dist[i][k] + Dist[k][j];
				}
			}
		} 
	}
}

void FindAnimal(MGraph Graph)
{
	WeightType Dist[MaxVertexNum][MaxVertexNum], MaxDist, MinDist;
	Vertex Animal, i;
	
	Floyd(Graph, Dist);
	
	MinDist = INFINITY;
	
	for(i = 0 ; i < Graph->NumberofVertex; i++){
		
		MaxDist = FindMaxDist(Dist, i, Graph->NumberofVertex);
		
		if(MaxDist == INFINITY){
			cout << "0" << endl;
			return;
		}
		
		if(MinDist > MaxDist){
			MinDist = MaxDist;
			Animal = i + 1; 
		}
	}
	
	cout << Animal << " " << MinDist;
}

WeightType FindMaxDist(WeightType Dist[][MaxVertexNum], Vertex i, int N)
{
	WeightType MaxDist = 0;
	Vertex j;
	
	for(j = 0; j < N; j++){
		if(i != j && Dist[i][j] > MaxDist) MaxDist = Dist[i][j];
	}
	
	return MaxDist;
}