CCF 网络延时 100分

痛定思痛。 2023-07-25 09:47 13阅读 0赞

题目传送门：[http://118.190.20.162/view.page?gpid=T24][http_118.190.20.162_view.page_gpid_T24]

1. 使用两次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;
    }

[http_118.190.20.162_view.page_gpid_T24]: http://118.190.20.162/view.page?gpid=T24