浙江大学数据结构MOOC-课后习题-第七讲-图4 哈利·波特的考试

题目汇总
浙江大学数据结构MOOC-课后习题-拼题A-代码分享-2024

题目描述

在这里插入图片描述

代码展示

照着教程视频来的，没啥好说的捏

#include <cstdlib>
#include <iostream>

#define MAXSIZE 100
#define IFINITY 65535
typedef int vertex;
typedef int weightType;

/* 边 */
struct ENode
{
	vertex V1, V2;
	weightType weight;
};
typedef ENode* ptrToENode;
typedef ptrToENode Edge;

/* 图结点 */
struct GNode
{
	int Nv;	/* 节点数 */
	int Ne;	/* 边数 */
	weightType G[MAXSIZE][MAXSIZE];	/* 邻接矩阵 */
};
typedef GNode* ptrToGNode;
typedef ptrToGNode MGraph;

MGraph creatGraph()
{	
	vertex V, W;
	MGraph G = (MGraph)malloc(sizeof(GNode));
	G->Ne = 0;
	std::cin >> G->Nv;

	for (V = 0; V < G->Nv; V++)
	{
		for (W = 0; W < G->Nv; W++)
		{
			G->G[V][W] = IFINITY;
		}
	}
	return G;
}

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 G = creatGraph();
	
	//插入边
	std::cin >> G->Ne;
	if (G->Ne != 0)
	{
		Edge E = (Edge)malloc(sizeof(ENode));
		for (int i = 0; i < G->Ne; i++)
		{
			std::cin >> E->V1 >> E->V2 >> E->weight;
			E->V1--;
			E->V2--;
			insertEdge(G, E);
		}
	}
	return G;
}

void floyd(MGraph Graph, weightType D[][MAXSIZE])
{
	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];
		}
	}

	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];
			}
		}	
	}
}

weightType findMaxDist(MGraph Graph, weightType D[][MAXSIZE], vertex i)
{
	weightType maxDist;
	vertex j;

	maxDist = 0;
	
	for (j = 0; j < Graph->Nv; j++)
	{
		if (D[i][j] > maxDist && i != j)
			maxDist = D[i][j];
	}
	return maxDist;
}
void findAnimal(MGraph G)
{	
	
	weightType D[MAXSIZE][MAXSIZE], maxDist, minDist;
	vertex animal, i;
	

	/* 利用Floyd求出任意两点间的最短路径长度 */
	floyd(G, D);
	
	/* 找出每行中的最大值， 然后从所有最大值中找出最小值 */
	minDist = IFINITY;
	for (i = 0; i < G->Nv; i++)
	{	
		maxDist = findMaxDist(G, D, i);
		if (maxDist == IFINITY)
		{
			std::cout << "0";
			return;
		}
		if (maxDist < minDist)
		{
			minDist = maxDist;
			animal = i + 1;
		}
	}
	std::cout << animal << ' ' << minDist;
}
int main()
{
	MGraph G = buildGraph();
	findAnimal(G);
	return 0;
}