CCF 网络延时 100分-蒲公英云

CCF 网络延时 100分

题目传送门：http://118.190.20.162/view.page?gpid=T24

使用两次Dijkstra，第一次从节点1出发，找到距离1最远的节点，设为U。再从U出发，找到距离U最远的节点，设为V。

答案就是从U到V的距离，也就是第二次Dijkstra得到的dis[v]。

提示：数组的长度应该是20000，而不是10000。应该是N+M。

#include<bits/stdc++.h>
#include<iostream>
#include<algorithm>
#include<string>
#include<vector>
#include<queue>
#include<set>
using namespace std;
const int MAXN = 20004;
const int INF = 100000000;
struct Choose{
    int u;
    int dis;
    Choose(int u,int dis){
        this->u = u;
        this->dis = dis;
    }
    bool operator<(const Choose &choose)const {
        return this->dis > choose.dis;
    }
};
vector<int> adj[MAXN];
int dis[MAXN];
bool vis[MAXN];
priority_queue<Choose> que;
int Dijkstra(int s,int n){
    fill(dis,dis+n+1,INF);
    dis[s] = 0;
    que.push(Choose(s,dis[s]));
    for(int i=1;i<=n;i++){
        int u = -1;
        do{
            if(!que.empty()){
                u = que.top().u;
                que.pop();
            }else{
                break;
            }
        }while(vis[u]);
        if(u == -1){
            return -1;
        }
        vis[u] = true;
        for(int j=0;j<adj[u].size();j++){
            int v = adj[u][j];
            if(!vis[v]){
                if(dis[v] > dis[u] + 1){
                    dis[v] = dis[u] + 1;
                    que.push(Choose(v,dis[v]));
                }
            }
        }
    }
    int maxDis = -1;
    int u = -1;
    for(int i=1;i<=n;i++){
        if(maxDis < dis[i]){
            u = i;
            maxDis = dis[i];
        }
    }
    return u;
} 
int main(){
    int n,m;
    int u,v;
    cin>>n>>m;
    for(int v=2;v<=n;v++){
        cin>>u;
        adj[u].push_back(v);
        adj[v].push_back(u);
    }
    for(int v=n+1;v<=n+m;v++){
        cin>>u;
        adj[u].push_back(v);
        adj[v].push_back(u);
    }
    n += m; 
    u = Dijkstra(1,n);
    fill(vis,vis+n+1,false);
    int index = Dijkstra(u,n);
    cout<<dis[index]<<endl;
    return 0;
}