本文主要是介绍PTA: 哈利·波特的考试，希望对大家解决编程问题提供一定的参考价值，需要的开发者们随着小编来一起学习吧！
题目
输入样例:
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 <cstdio>
#include <algorithm>
#include <queue>
#include <cstring>
#include <climits>using namespace std;const int maxn = 105;
struct Edge{int to, next, w;
}edge[105*105];
int head[105*105];
int tot = -1;
void add(int u, int v, int w) {++tot;edge[tot].to = v;edge[tot].w = w;edge[tot].next = head[u];head[u] = tot;
}
bool vis[maxn];
int dis[maxn];
int n, m;typedef pair<int, int> PII;
bool operator<(const PII& a, const PII& b) {return a.second > b.second;
}
priority_queue<PII> que;
int dij(int s) {fill(dis, dis+n+1, INT_MAX);dis[s] = 0;que.push({s, 0});while(que.size()) {auto tmp = que.top(); que.pop();for(int i = head[tmp.first]; i != -1; i = edge[i].next) {if(dis[edge[i].to] > tmp.second+edge[i].w) {dis[edge[i].to] = tmp.second+edge[i].w;que.push({edge[i].to, dis[edge[i].to]});}}}int mx = -1;for(int i = 1; i <= n; ++i)mx = max(mx, dis[i]);return mx;
}
int main(void)
{freopen("in.txt", "r", stdin);memset(head, -1, sizeof(head));scanf("%d%d", &n, &m);int u, v, w;for(int i = 0; i < m; ++i) {scanf("%d%d%d", &u, &v, &w);add(u, v, w);add(v, u, w);}int ans, mxl = 0x3f3f3f3f;for(int i = 1; i <= n; ++i) {int x = dij(i);for(int k = 1; k <= n; ++k) {if(dis[k] == INT_MAX) {printf("0");exit(0);}}if(x < mxl) {mxl = x;ans = i;}if(x == mxl)ans = min(ans, i);}printf("%d %d", ans, mxl);return 0;
}这篇关于PTA: 哈利·波特的考试的文章就介绍到这儿，希望我们推荐的文章对编程师们有所帮助！
