题目链接
大意:给你一个无向图,k个特殊点,你要在两个不同的特殊点直接连一条无向边,使得 1 > n 1->n 1>n的最短路最长。
思路:直观的想法肯定是枚举所有情况来找到最小值,显然复杂度不允许。我们思考一下:
不连边的最短路是 l e n len len,当前两个特殊点分别是 s , t s,t s,t,那么这种情况下的最短路就是
m i n ( l e n , m i n ( p [ s ] + q [ t ] + 1 , p [ t ] + q [ s ] + 1 ) ) min(len,min(p[s]+q[t]+1,p[t]+q[s]+1)) min(len,min(p[s]+q[t]+1,p[t]+q[s]+1)),p数组表示 1 1 1出发的最短路,q表示从n出发的最短路。
如果可以确定 p [ s ] + q [ t ] + 1 , p [ t ] + q [ s ] + 1 p[s]+q[t]+1,p[t]+q[s]+1 p[s]+q[t]+1,p[t]+q[s]+1的大小的话,是不是就可以只扫一遍啦。
显然我们排个序即可,排序规则是 p [ s ] + q [ t ] + 1 < p [ t ] + q [ s ] + 1 p[s]+q[t]+1<p[t]+q[s]+1 p[s]+q[t]+1<p[t]+q[s]+1
然后遍历一下k个特殊点:那么当前遍历到的t,那么t与之前所有的点直接的最短路都是 m i n ( p [ s ] + q [ t ] + 1 , l e n ) min(p[s]+q[t]+1,len) min(p[s]+q[t]+1,len),把 p [ s ] p[s] p[s]的最大值记录一下即可。
细节见代码:

#include <bits/stdc++.h>
using namespace std;
typedef long long LL;
const int N = 2e5 + 10;
#define fi first
#define se second
#define pb push_back
int n,m,k;
vector<int>v[N];
int a[N],inq[N];
int dis[2][N];
void spfa(int s,int c){
  queue<int>q;
  for(int i=1;i<=n;i++)dis[c][i]=1e9,inq[i]=0;
  dis[c][s]=0;
  q.push(s);
  while(!q.empty()){
    int x=q.front();
    inq[x]=0;
    q.pop();
    for(auto k:v[x]){
      if(dis[c][k]>dis[c][x]+1){
        dis[c][k]=dis[c][x]+1;
        if(!inq[k]){
          inq[k]=1;
          q.push(k);
        }
      }
    }
  }
}
int main() {
  ios::sync_with_stdio(false);
  cin>>n>>m>>k;
  for(int i=1;i<=k;i++)cin>>a[i];
  for(int i=1;i<=m;i++){
    int s,t;
    cin>>s>>t;
    v[s].pb(t);
    v[t].pb(s);
  }
  spfa(1,0);
  spfa(n,1);
  int ans=0;
  sort(a+1,a+1+k,[](int x,int y){
    return dis[0][x]-dis[1][x]<dis[0][y]-dis[1][y];
  });
  int pat=dis[0][a[1]];
  for(int i=2;i<=k;i++){
    ans=max(ans,pat+dis[1][a[i]]+1);
    pat=max(pat,dis[0][a[i]]);
  }
  cout<<min(ans,dis[0][n])<<'\n';
  return 0;
}