题意:
给n,m,k,有n个点,m条线,距离都是一;
有k个特殊点,选择其中两个,进行相连,距离变为1,使得原本的最短路,经过相连改变小或者不变,最终结果是所有结果里面的最大距离。
思路:
选择i,j两个点(满足从1出发先遇到 i ,在遇到 j ),1~i+j~n+1就是新的最短路(1~i表示 1 到 i 最短距离,j~n表示 j 到 n 最短距离)
所以只要算出1到所有点的最短距离dis[0][N] 和 n到所有点的最短距离dis[1][N],再选择特殊点进行相连,因为最大化的话,肯定是要选择两个特殊点靠得近的排序
同时,满足特殊点按照从1出发先遇到的顺序来,因为可能是先遇到 j 点,导致 会有1~i+j~n+1>1~j+i~n+1的情况
比较就用1~i+j~n<1~j+i~n,然后操作有点像尺缩,叙述能力有限
最后还要进行与1~n进行比较大小,这个用图解释比较直观
#include<bits/stdc++.h>
using namespace std;
#define ll long long
#define il inline
#define it register int
#define inf 0x3f3f3f3f
#define lowbit(x) (x)&(-x)
#define mem(a,b) memset(a,b,sizeof(a))
#define mod 998244353
const int N=2e5+;
struct node{
int v,next;
}d[N<<];
struct node1{
int x,bu;
node1(){}
node1(int xx,int buu):x(xx),bu(buu){}
friend bool operator<(const node1 a,const node1 b){
if(a.bu==b.bu){
return a.x>b.x;
}
return a.bu>b.bu;
}
};
int n,m,k;
int a[N],head[N],tot;
int dis[][N];
il void add(int u,int v){
d[tot].v=v;d[tot].next=head[u];
head[u]=tot++;
}
void bfs(int x,int c){
dis[c][x]=;
priority_queue<node1>q;
q.push(node1(x,));
while(!q.empty()){
node1 t=q.top();q.pop();
int u=t.x,bu=t.bu;
for(it i=head[u];~i;i=d[i].next){
int v=d[i].v;
if(dis[c][v]==-){
dis[c][v]=bu+;
q.push(node1(v,bu+));
}
}
}
}
bool cmp(int x,int y){
return dis[][x]+dis[][y]<dis[][y]+dis[][x];
}
int main(){
tot=;
scanf("%d%d%d",&n,&m,&k);
for(it i=;i<=n;i++){head[i]=-,dis[][i]=dis[][i]=-;}
for(it i=;i<k;i++){
scanf("%d",&a[i]);
}
for(it i=;i<m;i++){
int u,v;scanf("%d%d",&u,&v);
add(u,v),add(v,u);
}
bfs(,);bfs(n,);
sort(a,a+k,cmp);
int ans=dis[][a[]],da=-;
for(it i=;i<k;i++){
da=max(da,ans+dis[][a[i]]+);
ans=max(ans,dis[][a[i]]);
}
printf("%d\n",min(dis[][n],da));
return ;
}
/*
5 5 2
2 4
1 5
4 5
3 4
2 3
1 2
*/