cf 621D

CF 621D

题目链接

题目大意:

给一个图，n个点m个边，给出k个特殊点，保证图联通，让在特殊点中选一对点连起来，求连完后的1到n节点的最短路的最大值。
，，，怎么做呢？
朴素做法： 显然是预处理1~每个结点的最短路，n到每个结点的最短路，然后枚举k里的两个节点，连起来，取最大值，然后最后跟原来的最短路取最小值就好了，但是这个复杂度是k^2。
显然不行，于是想一下怎么优化，，，

就是这里，想不到了，短路了，自闭了，掉分了，没了。。。
赛后看大佬题解：
设选的点为x和y，1到i节点的最短路为dis[0][i] n到i节点的最短路为dis[1][i]；
过x，y的最短路为min(dis[0][x] + dis[1][y] + 1, dis[1][x] + dis[0][y] + 1);
这个很显然，
若符合条件dis[0][x] + dis[1][y] + 1 <= dis[1][x] + dis[0][y] + 1 ，
也就是dis[0][x] - dis[1][x] <= dis[0][y] - dis[1][y] ，最短路就为dis[0][x]+dis[1][y] + 1
于是就可以先按dis[0][x] - dis[1][x] 排个序，因为要求的是最短路的最大值，所以枚举x找符合条件也就是排完序后在x前面的，y的dis[1][y] 的最大值然后加dis[0][x] + 1就是过x节点的最大的最短路，
上代码

#include<stdio.h>
#include<algorithm>
#include<vector>
#include<queue>
using namespace std;

const int maxn = 2e5+5; 
int dis[2][maxn];
int a[maxn];
vector<int> vv[maxn];
void bfs(int f,int x)
{
   
	queue<int> qq;
	qq.push(x);
	dis[f][x] = 1;
	while(!qq.empty())
	{
   
		int t = qq.front();
		qq.pop();
		for (int i = 0; i < vv[t].size(); i ++ )
		{
   
			int p = vv[t][i];
			if(dis[f][p])
				continue;
			dis[f][p] = dis[f][t] + 1;
			qq.push(p);
		}
	}
}
struct Node
{
   
	int num,id;
	bool operator< (const Node & a)const{
   
		return num < a.num;
	}
	Node(int a,int b)
	{
   
		num = a;
		id = b;
	}
};
vector<Node> vp;
int main()
{
   
	int n,m,k;
	scanf("%d%d%d",&n,&m,&k);
	for (int i = 1; i <= k; i ++ )
	{
   
		scanf("%d",&a[i]);
	}
	for (int i = 1; i <= m; i ++ )
	{
   
		int x,y;
		scanf("%d%d",&x,&y);
		vv[x].push_back(y);
		vv[y].push_back(x);
	}
	bfs(0,1);
	bfs(1,n);
	for (int i = 1; i <= n; i ++ )
	{
   
		dis[0][i] -- ;
		dis[1][i] -- ;
// printf("%d %d %d\n",i,dis[0][i],dis[1][i]);
	}
	for (int i = 1; i <= k; i ++ )
	{
   
		vp.push_back(Node(dis[0][a[i]] - dis[1][a[i]],a[i]));
	}
	sort(vp.begin(),vp.end());
	int ans =0 ;
	int temp = 0;
	for (int i = 0; i < k; i ++ )
	{
   
// printf("%d %d\n",vp[i].id,vp[i].num);
		if(i > 0)
			ans = max(ans,dis[1][vp[i].id] + temp + 1);
		temp = max(temp,dis[0][vp[i].id]);
	}
	printf("%d\n",min(ans,dis[0][n]));
}