题目链接戳这里
欲求源点到其它点最短距离最长的那个点.
一开始直接dijkstra..超时.换BFS就过了,在BFS过程保存第一个距离最大的点
用邻接矩阵实现的dijkstra算法复杂度是O(|V|^2),用邻接表更新最短距离的时候是O(|E|),但是每次都要枚举所有的顶点来查找下一个应该使用的顶点,所以最终还是O(|V|^2),用堆优化的dijkstra可以变成O(|E|log|V|) 而bfs是O(|V|+|E|).
#include <iostream>
#include <bits/stdc++.h>
using namespace std;
#define mst(a,b) memset(a,b,sizeof(a))
#define rep(i,a,b) for(int i=(a);i<(b);++i)
const int inf = 0x3f3f3f3f, maxN = 10005;
int N, M, K;
vector<int> G[maxN];
int d[maxN], vis[maxN], max_d;
void link(int u, int v) {
G[u].push_back(v);
G[v].push_back(u);
}
int bfs(int s) {
mst(vis, 0);
vis[s] = 1;
d[s] = 0;
int id = s, dis = 0;
queue<int> Q;
Q.push(s);
while (!Q.empty()) {
int t = Q.front(); Q.pop();
if (d[t] > dis) {
dis = d[t];
id = t;
}
rep(i, 0, G[t].size()) {
int ch = G[t][i];
if (!vis[ch]) {
d[ch] = d[t] + 1;
vis[ch] = 1;
Q.push(ch);
}
}
}
return (dis == 0) ? 0 : id + 1;
}
int main() {
// freopen("data.in", "r", stdin);
scanf("%d%d%d", &N, &M, &K);
int a, b;
rep(i, 0, M) {
scanf("%d%d", &a, &b);
link(a - 1, b - 1);
}
rep(i, 0, K) {
scanf("%d", &a);
a--;
if (i) printf("\n");
printf("%d", bfs(a));
}
return 0;
}
