D. Cow and Fields(最短路+思维)

Problem - 1307D - Codeforces

题意:给你n个点m条双向边的图,每条边边权为1,你必须从k个点中选两个点连接,使得连接后,

找到1到n的最短路径的最大可能长度。

题解:

如果直接从k个点中枚举是肯定不行的

由于要选两个点进行连接,我们可以这样理解(因为我们不知道1首先到达的是连接的哪个点)

1 -> i  -> j  -> n 

1 -> j  -> i - > n

设d1[i]为1到其他任何点的距离,dn[i]为n到其他任何点的距离

假设是第一种情况

d1[i] +dn[j] +1<= d1[j] +dn[i] +1

我们可以把它变形一下d1[i] - dn[i] <= d1[j] -dn[j]

也就是说要想d1[i] + dn[j] + 1最大

1到一个点的距离-n到一个点的距离小的要排在前面

因为从小到大排序后,我们可以发现d1[j] 加上排在j前面的最大dn[i]一定是当前最大的

#include
#include
#include
#include 
#include
#include
#include
#include
using namespace std;
typedef pair<int,int> PII;
int n,m,k;
int p[200050];
int d[3][200050];
int vis[200050];
int idx,ne[400050],h[400050],e[400050];
void add(int l,int r)
{
	e[idx] = r;
	ne[idx] = h[l];
	h[l] = idx ++;
}
void djk(int st,int x)
{
	priority_queue,greater> q;
	q.push({0,st});
	memset(vis,0,sizeof vis);
	d[x][st] = 0;
	while(q.size())
	{
		PII k = q.top();
		q.pop();
		int ver = k.second,dis = k.first;
		if(vis[ver])
		continue;
		vis[ver] = 1;
		for(int i = h[ver];i!=-1;i = ne[i])
		{
			int j = e[i];
			if(d[x][j] > dis + 1)
			{
				d[x][j] = dis +1;
				q.push({d[x][j],j});
			}
		}
	}
}
int main()
{
	cin >> n >> m>> k;
	memset(h,-1,sizeof h);
	memset(d,0x3f,sizeof d);
	for(int i = 1;i <= k;i++)
	{
		cin >> p[i];
	}
	for(int i = 1; i <= m;i++)
	{
		int l,r;
		cin >> l >>r;
		add(l,r);
		add(r,l);
	}
	djk(1,0);
	djk(n,1);
	vector q;
	for(int i = 1;i <= k;i++)
	{
		q.push_back({d[0][p[i]]-d[1][p[i]],d[1][p[i]]}); 
	}	
	int ma = 0;
	int ans = 0;
	sort(q.begin(),q.end());
	for(int i = 0;i < k;i++)
	{
		if(i)
		{
			ans = max(ans,ma + q[i].second+1); 
		}
		ma = max(ma,q[i].second+q[i].first);
	}
	cout <<min(ans,d[0][n]);
	
	
}