本文主要是介绍pta 哈利·波特的考试 (25 分)(Floyd弗洛伊德算法)(列出坑点),希望对大家解决编程问题提供一定的参考价值,需要的开发者们随着小编来一起学习吧!
哈利·波特要考试了,他需要你的帮助。这门课学的是用魔咒将一种动物变成另一种动物的本事。例如将猫变成老鼠的魔咒是haha,将老鼠变成鱼的魔咒是hehe等等。反方向变化的魔咒就是简单地将原来的魔咒倒过来念,例如ahah可以将老鼠变成猫。另外,如果想把猫变成鱼,可以通过念一个直接魔咒lalala,也可以将猫变老鼠、老鼠变鱼的魔咒连起来念:hahahehe。
现在哈利·波特的手里有一本教材,里面列出了所有的变形魔咒和能变的动物。老师允许他自己带一只动物去考场,要考察他把这只动物变成任意一只指定动物的本事。于是他来问你:带什么动物去可以让最难变的那种动物(即该动物变为哈利·波特自己带去的动物所需要的魔咒最长)需要的魔咒最短?例如:如果只有猫、鼠、鱼,则显然哈利·波特应该带鼠去,因为鼠变成另外两种动物都只需要念4个字符;而如果带猫去,则至少需要念6个字符才能把猫变成鱼;同理,带鱼去也不是最好的选择。
输入格式:
输入说明:输入第1行给出两个正整数N (≤100)和M,其中N是考试涉及的动物总数,M是用于直接变形的魔咒条数。为简单起见,我们将动物按1~N编号。随后M行,每行给出了3个正整数,分别是两种动物的编号、以及它们之间变形需要的魔咒的长度(≤100),数字之间用空格分隔。
输出格式:
输出哈利·波特应该带去考场的动物的编号、以及最长的变形魔咒的长度,中间以空格分隔。如果只带1只动物是不可能完成所有变形要求的,则输出0。如果有若干只动物都可以备选,则输出编号最小的那只。
输入样例:
6 11
3 4 70
1 2 1
5 4 50
2 6 50
5 6 60
1 3 70
4 6 60
3 6 80
5 1 100
2 4 60
5 2 80
输出样例:
4 70
思路:
先初始化邻接矩阵,再用弗洛伊德算法找出所有点的所有的最短路径,再根据题意提取需要的数据。
注意:
这道题坑还是挺多的,我基本上全都踩了一遍🤦♂️,千万要认真读题呀,在这里把踩了的坑列了一下,大家也注意一下
1.由于反方向的魔咒与正方向的魔咒长度相等,因此该图为无向图,注意初始化邻边矩阵是要对两边都初始化
2.注意题目要求如果图不连通则输出0,因此需要检测图是否连通
3.题目要求带去的动物可以让最难变的那种动物需要的魔咒最短,也就是说要找的点的最长路径是所有的点的最大路径中最短的
4.动物编号从1开始,太反程序猿了😡
代码:
#include <iostream>
#define INF 0x3f3f3f3f //定义INF作为两点之间不相连的标志
using namespace std;int Matrix[101][101]; //定义邻接矩阵void Floyd(int n){ //弗洛伊德算法求所有点的所有最小路径for(int u=1; u <= n; u++){ //第一层循环遍历所有点for(int v=1; v <= n; v++){ //二三层循环遍历邻接矩阵,按照权重找出u到所有点的最小路径for(int w=1; w <= n; w++){if(Matrix[v][w] > Matrix[v][u] + Matrix[u][w]){//v->w的距离大于v->u->vMatrix[v][w]= Matrix[v][u] + Matrix[u][w];Matrix[w][v]= Matrix[v][u] + Matrix[u][w];}}}}
}
void findAnimal(int n){ //找到所需的动物int needV=0,needMax=INF; //所需点的坐标,所需点的最长路径for(int u=1; u <= n; u++){ //第一层循环遍历所有点int maxLen=0; //u的最大路径for(int v=1; v <= n; v++){ //遍历u到所有点的所有路径,找到最大路径if(Matrix[v][u] == INF){ //如果图不连通,直接输出0,注意对角线上的点为INFcout<<0<<endl;return;}else if(Matrix[v][u]>maxLen) //找u点的最大路径maxLen=Matrix[v][u];}if(maxLen<needMax){ //找到所有点的最大路径中的最小值,并记录该点needMax=maxLen;needV=u;}}cout << needV << ' ' << needMax << endl;
}
void iniMatrix(int n, int e){ //初始化邻接矩阵int x,y,w;while (e--){cin>>x>>y>>w;Matrix[x][y]=w;Matrix[y][x]=w;}for(int i=1; i <= n; i++){for(int j=1; j <= n; j++){if(!Matrix[i][j]&& i!=j) //注意对角线上的点不要设为INF,可以省不少麻烦Matrix[i][j]=INF;}}
}
int main(){int n,e;cin >> n >> e;iniMatrix(n, e);Floyd(n);findAnimal(n);
}
AC图:
这篇关于pta 哈利·波特的考试 (25 分)(Floyd弗洛伊德算法)(列出坑点)的文章就介绍到这儿,希望我们推荐的文章对编程师们有所帮助!