GPLT L3-008. 喊山 BFS模板

题目链接戳这里
欲求源点到其它点最短距离最长的那个点.
一开始直接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;
}