Cow and Fields(最短路思维）

题意：

思路：
首先说一些性质，比如我们操作a,b点，如果a,b不在1~n的最短路径上，那么对答案是没有贡献的。如果在1到n的最短路径上呢？也就是我们要求Max(dist[a]+dist2[b]+1),dist1代表从1开始bfs，dist2代表从n开始bfs最短路径，O(n^2)枚举肯定不好，我们可以按照dist[a]-dist2[a]排序一下，然后这个答案就可以O(N)枚举得到了，我们在枚举的时候记录一下最大的dist[x]，当前的dist2[b]已经固定了，更新一下答案就好了，最后注意要和原本图的最短路取一个min。

// Problem: 最大化最短路
// Contest: AcWing
// URL: https://www.acwing.com/problem/content/3800/
// Memory Limit: 256 MB
// Time Limit: 1000 ms
// 
// Powered by CP Editor (https://cpeditor.org)

#include<bits/stdc++.h>
#define IL inline
#define x first
#define y second
typedef long long ll;
using namespace std;
const int N=400010;
int h[N],ne[N],idx,e[N];
void add(int a,int b)
{
	e[idx]=b,ne[idx]=h[a],h[a]=idx++;
}
int dist1[N];
int dist2[N];
int a[N];int n,m,k;
void bfs(int s,int dist[])
{
	memset(dist,0x3f,4*N);
	queue<int>q;
	q.push(s);
	dist[s]=0;
	// cout<<s<<endl;
	while(q.size())
	{
		auto t=q.front();
		q.pop();
		for(int i=h[t];~i;i=ne[i])
		{
			int j=e[i];
			// cout<<t<<" "<<j<<endl;
			if(dist[j]>dist[t]+1)
			{
				dist[j]=dist[t]+1;
				q.push(j);
				
			}
		}
	}
}
int main()
{
	memset(h,-1,sizeof h);
	
	cin>>n>>m>>k;
	for(int i=1;i<=k;i++)	cin>>a[i];
	while(m--)
	{
		int a,b;
		cin>>a>>b;
		add(a,b);
		add(b,a);
	}
	bfs(1,dist1);
	bfs(n,dist2);
	// for(int i=1;i<=n;i++)	cout<<dist1[i]<<" ";
	// cout<<endl;
	int res=dist1[n];
	// for(int i=1;i<=k;i++)
		sort(a+1,a+1+k,[&](int a,int b)
		{
			return dist1[a]-dist2[a]<dist1[b]-dist2[b];
		});
	int ans=0;
	int mx=0;
	for(int i=1;i<=k;i++)
	{
		if(i>1)
		ans=max(ans,mx+dist2[a[i]]+1);
		mx=max(mx,dist1[a[i]]);
	}
	// cout<<res<<endl;
	// cout<<ans<<endl;
	cout<<min(ans,res)<<endl;
    return 0;
}

最后

以上就是受伤衬衫为你收集整理的Cow and Fields(最短路思维）的全部内容，希望文章能够帮你解决Cow and Fields(最短路思维）所遇到的程序开发问题。

如果觉得靠谱客网站的内容还不错，欢迎将靠谱客网站推荐给程序员好友。