2019牛客多校第四场 A meeting

链接：https://ac.nowcoder.com/acm/contest/884/A
来源：牛客网

时间限制：C/C++ 1秒，其他语言2秒
空间限制：C/C++ 524288K，其他语言1048576K
64bit IO Format: %lld

题目描述

A new city has just been built. There're

In order to save resources, only exactly

There is one person in each of the places numbered

x1,x2…xkx_1,x_2 \ldots x_kx1​,x2​…xk​ and they've decided to meet at one place to have a meal. They wonder what's the minimal time needed for them to meet in such a place. (The time required is the maximum time for each person to get to that place.)

输入描述:

First line two positive integers,

For each the following

On the following line there're

x1,x2…xkx_1,x_2 \ldots x_kx1​,x2​…xk​ separated by spaces. These are the numbers of places the persons are at.

输出描述:

A non-negative integer - the minimal time for persons to meet together.

示例1

输入

复制

输出

复制

说明

They can meet at place 1 or 3.
1<=n<=1e5

题意

给出一颗树和一些点,一个点到另一个点的距离为1,求这些点在树上最大距离的一半

思路
要求图上的最大距离可先任意取一个点求最大距离,再从最大距离的这个点再找一次最大距离(因为重新求的最大距离必定大于或等于原先的最大距离)
这里求最大距离用了边权取负再dijkstra,把求出的最小负距离取反就得到最大正距离

代码

 1 #include<bits/stdc++.h>
 2 using namespace std;
 3 const int amn=2e5+5,inf=0x3f3f3f3f;
 4 int n,k,dis[amn];
 5 int p[amn];
 6 struct node{
 7     int pos,val;
 8     bool operator <(const node &a)const {return a.val<val;}
 9 };
10 struct edge{
11     int to,w,next;
12 }e[amn];
13 priority_queue<node> que;
14 int head[amn],edgenum=0,vis[amn];
15 void add(int f,int t,int co)
16     {
17         e[++edgenum].next=head[f];
18         head[f]=edgenum;
19         e[edgenum].to=t;
20         e[edgenum].w=co;
21     }
22 void Dijkstra(int s)
23     {
24         memset(dis,0x3f,sizeof(dis));
25         memset(vis,0,sizeof vis);
26         while(que.size())que.pop();
27         dis[s]=0;
28         node a;
29         a.pos=s,a.val=dis[s];
30         que.push(a);
31         while(!que.empty())
32             {
33                 node x=que.top();que.pop();
34                 int u = x.pos;
35                 if(x.val > dis[u]) continue;
36                 vis[u]=true;
37                 for(int i=head[u];i!=-1;i=e[i].next)
38                     {
39                         int v=e[i].to;
40                         if(vis[v])    continue;
41                         if(dis[v]>e[i].w+dis[u])
42                             {
43                                 dis[v]=e[i].w + dis[u];
44                                 a.pos=v,a.val=dis[v];
45                                 que.push(a);
46                             }
47                     }
48             }
49     }
50 int main(){
51     memset(head,-1,sizeof head);
52     ios::sync_with_stdio(0);
53     cin>>n>>k;
54     int u,v,ans;
55     for(int i=1;i<n;i++){
56         cin>>u>>v;
57         add(u,v,-1);
58         add(v,u,-1);
59     }
60     for(int i=1;i<=k;i++){
61         cin>>p[i];
62     }
63     Dijkstra(p[1]);
64     int maxn=inf,maxi=0;
65     for(int i=1;i<=k;i++){
66         if(dis[p[i]]<maxn){
67             maxn=dis[p[i]];
68             maxi=i;
69         }
70     }
71     Dijkstra(p[maxi]);
72     ans=inf;
73     for(int i=1;i<=k;i++){
74         if(dis[p[i]]<ans){
75             ans=dis[p[i]];
76         }
77     }
78     ans=-ans;
79     printf("%d\n",ans/2+ans%2);
80 }