【中国大学MOOC-陈越|哈利波特的考试】
文章图片
输入样例:
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
结尾无空行
代码：
#include
#define Maxsize 101
#define INF 65535
using namespace std;
int animal[Maxsize][Maxsize];
int N,M;
int main()
{
cin >> N >> M;
for (int i = 0;
i <=N;
i++) {
for (int j = 0;
j <= N;
j++) {
if (i == j) {
animal[i][j] = 0;
}
else {
animal[i][j] = INF;
}
}
}
for (int k = 0;
k < M;
k++) {
inti, j, length;
cin >> i >> j >> length;
animal[i][j] = animal[j][i] = length;
}
//核心代码Floyd算法
//得出所有顶点到所有顶点的最短路径
for (int k = 1;
k <= N;
k++) {
for (int i = 1;
i <= N;
i++) {
for (int j = 1;
j <= N;
j++) {
if (animal[i][j] > animal[i][k] + animal[k][j]) {
animal[i][j] = animal[i][k] + animal[k][j];
}
}
}
}
int index = 0;
int min = INF;
int max;
for (int i = 1;
i <= N;
i++) {
max = 0;
for (int j = 1;
j <= N;
j++) {
if (max <= animal[i][j]) {
max = animal[i][j];
}
}
if (min > max) {
min = max;
index = i;
}
}
//当有无法变成的动物时，max会等于INF
if (index == 0) {
cout <<"0"<< endl;
}
else {
cout << index << " " << min;
}
return 0;
}
推荐阅读
- 后端|Spring Cloud（Dubbo？还是K8s？）
- 算法分析与设计|算法系列——二分查找（例题）
- 数据结构|查找算法——二分查找（原理+源码）
- C++篇|【C++进阶】第十九篇——红黑树（概念+代码实现）
- Redis数据库|布隆过滤器原理
- 面试题目|面试题七 C/C++ 骑士营救公主 骑士只能向右或者向下移动，遇到陷阱就死了，求骑士营救公主的所有路线-程序员面试题
- 数据结构与算法|《程序员》算法擂台（骑士聚会）
- python|Yolo4-Tiny代码解读
- 算法|哈工大算法设计与分析总结