Solution #

First let’s use BFS to find the distance from node $1$ and node $n$ to all nodes. Let $x_i$ be the distance to node $1$ and $y_i$ be the distance to node $n$ .

Now we want to choose two nodes $a$ and $b$ such that $\min(x_a+y_b,x_b+y_a)$ is maximized. Without losing generality, assume $x_a+y_b\leq x_b+y_a$ . That is to say we want to maximize $x_a+y_b$ subject to $x_a+y_b\leq x_b+y_a$ . So we can sort by $x_i-y_i$ and iterate over $y$ while keeping the maximum value of $x_a$ before $y_b$ .

Also note that the answer cannot be bigger than the distance between node $1$ and $n$ .

Code #

#include <bits/stdc++.h>
 
#define forn(i, n) for (int i = 0; i < int(n); ++i)
#define for1(i, n) for (int i = 1; i <= int(n); ++i)
#define fore(i, l, r) for (int i = int(l); i <= int(r); ++i)
#define ford(i, n) for (int i = int(n)-1; i >= 0; --i)
#define pb push_back
#define eb emplace_back
#define ms(a, x) memset(a, x, sizeof(a))
#define F first
#define S second
#define endl '\n'
#define all(x) (x).begin(),(x).end()
#define de(x) cout<<#x<<" = "<<(x)<<endl
#define de2(x,y) cout<<#x<<" = "<<(x) <<' '<< #y<<" = "<<y<<endl;
 
using namespace std;
 
typedef long long ll;
typedef pair<int, int> pii;
constexpr int INF = 0x3f3f3f3f;
mt19937 gen(chrono::high_resolution_clock::now().time_since_epoch().count());
 
const int N=2e5+5;
vector<int> G[N];
void bfs(vector<int>& dis,int s){
	queue<int> q;
	q.push(s);
	dis[s]=0;
	while(!q.empty()){
		int now=q.front();
		q.pop();
		for(int next:G[now]){
			if(dis[next]==INF){
				dis[next]=dis[now]+1;
				q.push(next);
			}
		}
	}
}
int main() {
	ios::sync_with_stdio(false);
	cin.tie(nullptr);
	int n,m,k;
	cin>>n>>m>>k;
	vector<int> sp(k);
	for(auto& it:sp) cin>>it;
	forn(i,m){
		int x,y;
		cin>>x>>y;
		G[x].pb(y);
		G[y].pb(x);
	}
	vector<int> dis1(n+1,INF),dis2(n+1,INF);
	bfs(dis1,1);
	bfs(dis2,n);
	vector<pii> data(k);
	forn(i,k) data[i]={dis1[sp[i]]-dis2[sp[i]],sp[i]};
	sort(all(data));
	int best=0,mx=-INF;
	for(auto it:data){
		int a=it.S;
		best=max(best,mx+dis2[a]);
		mx=max(mx,dis1[a]);
	}
	cout<<min(dis1[n],best+1);
	return 0;
}

Solution for CodeForces 1307D - Cow and Fields

Solution #

Code #