传送门：CodeForces-1307D
题目描述
Bessie is out grazing on the farm, which consists of n fields connected by m bidirectional roads. She is currently at field $1$, and will return to her home at field $n$ at the end of the day.
The Cowfederation of Barns has ordered Farmer John to install one extra bidirectional road. The farm has $k$ special fields and he has decided to install the road between two different special fields. He may add the road between two special fields that already had a road directly connecting them.
After the road is added, Bessie will return home on the shortest path from field $1$ to field $n$. Since Bessie needs more exercise, Farmer John must maximize the length of this shortest path. Help him!
输入描述
The first line contains integers $n$, $m$, and $k$ $(2≤n≤2⋅10^5, n−1≤m≤2⋅10^5, 2≤k≤n)$ — the number of fields on the farm, the number of roads, and the number of special fields.
The second line contains $k$ integers $a_1,a_2,…,a_k$ $(1≤a_i≤n)$ — the special fields. All $a_i$ are distinct.
The $i$-th of the following m lines contains integers xi and yi (1≤xi,yi≤n, xi≠yi), representing a bidirectional road between fields $x_i$ and $y_i$.
It is guaranteed that one can reach any field from every other field. It is also guaranteed that for any pair of fields there is at most one road connecting them.
输出描述
Output one integer, the maximum possible length of the shortest path from field $1$ to $n$ after Farmer John installs one road optimally.
思路分析
$d1[i]$表示从$1$到$i$的最短距离
$d2[i]$表示从$1$到$i$的最短距离
对于选择的两个点$i,j$
如果对答案有影响，那么影响为$min(d1[i]+1+d2[j],d1[j]+1+d2[i])$
如果枚举$i,j$的话肯定会超时
观察以上的式子，经过移项之后为$d1[i]-d2[j]<d1[j]-d2[j]$
令$F[x]=d1[x]-d2[x]$
可以得出，两个关键点，优先选取$F[x]$小的那个点
对关键点按$F[x]$排序，枚举$j$,对于每个$j$答案等于$j$之前的$d1[i]+1+d2[j]$
最后再与初始的$d1[n]$取最小值就是答案
样例输入
5 5 3
1 3 5
1 2
2 3
3 4
3 5
2 4
样例输出
3
AC代码
#include <functional>
#include <algorithm>
#include <iostream>
#include <cstring>
#include <cstdlib>
#include <iomanip>
#include <vector>
#include <string>
#include <cstdio>
#include <queue>
#include <stack>
#include <cmath>
#include <map>
#include <set>
#if __cplusplus >= 201103L
#include <unordered_map>
#include <unordered_set>
#endif
#define ls x<<1
#define rs x<<1|1
#define fi first
#define se second
#define ll long long
#define pb push_back
#define mp make_pair
#define fun function
#define vi vector<int>
#define lowbit(x) x&(-x)
#define pii pair<int,int>
#define all(x) x.begin(),x.end()
#define mem(a,b) memset(a,b,sizeof(a))
#define IOS ios_base::sync_with_stdio(0); cin.tie(0);cout.tie(0);
using namespace std;
const int INF = 0x3f3f3f3f;
const int N=1e6+10;
vector<int>e[N];
int n,m,k;
int vis[N],d1[N],d2[N],p[N];
void spfa(int s,int *dis) {
for(int i=0; i<=n; i++) {
dis[i]=INF;
vis[i]=0;
}
queue<int>q;
q.push(s);
dis[s]=0;
while(!q.empty()) {
int u=q.front();
q.pop();
vis[u]=0;
for(auto v:e[u]) {
if(dis[v]>dis[u]+1) {
dis[v]=dis[u]+1;
if(!vis[v]) {
vis[v]=1;
q.push(v);
}
}
}
}
}
int cmp(int a,int b) {
return d1[a]-d2[a]<d1[b]-d2[b];
}
int main() {
IOS;
#ifdef xiaofan
freopen("1.in","r",stdin);
freopen("1.out","w",stdout);
#endif
cin>>n>>m>>k;
for(int i=0; i<k; i++)
cin>>p[i];
for(int i=0; i<m; i++) {
int u,v;
cin>>u>>v;
e[u].pb(v);
e[v].pb(u);
}
spfa(1,d1);
spfa(n,d2);
sort(p,p+k,cmp);
int ma=d1[p[0]];
int ans=-1;
for(int i=1; i<k; i++) {
ans=max(ans,ma+d2[p[i]]+1);
ma=max(ma,d1[p[i]]);
}
cout<<min(d1[n],ans)<<endl;
return 0;
}
