Cow and Fields （CodeForces-1307D）（SPFA最短路）
Bessie is out grazing on the farm, which consists of nn fields connected by mm bidirectional roads. She is currently at field 11, and will return to her home at field nn at the end of the day.
The Cowfederation of Barns has ordered Farmer John to install one extra bidirectional road. The farm has kk 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 11 to field nn. Since Bessie needs more exercise, Farmer John must maximize the length of this shortest path. Help him!
Input
The first line contains integers nn, mm, and kk (2≤n≤2⋅1052≤n≤2⋅105, n−1≤m≤2⋅105n−1≤m≤2⋅105, 2≤k≤n2≤k≤n) — the number of fields on the farm, the number of roads, and the number of special fields.
The second line contains kk integers a1,a2,…,aka1,a2,…,ak (1≤ai≤n1≤ai≤n) — the special fields. All aiai are distinct.
The ii-th of the following mm lines contains integers xixi and yiyi (1≤xi,yi≤n1≤xi,yi≤n, xi≠yixi≠yi), representing a bidirectional road between fields xixi and yiyi.
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
Output one integer, the maximum possible length of the shortest path from field 11 to nn after Farmer John installs one road optimally.
Examples
Input
5 5 3 1 3 5 1 2 2 3 3 4 3 5 2 4
Output
3
Input
5 4 2 2 4 1 2 2 3 3 4 4 5
Output
3
Note
The graph for the first example is shown below. The special fields are denoted by red. It is optimal for Farmer John to add a road between fields 33 and 55, and the resulting shortest path from 11 to 55 is length 33.
The graph for the second example is shown below. Farmer John must add a road between fields 22 and 44, and the resulting shortest path from 11 to 55 is length 33.
题意：给定一个n个点m条双向边的图，这n个点有k个特殊的点，可以在这k个点中找两个点连一条双向虚边。问从1到n的最短路最大是多少。每条边的距离是1。
思路：这道题的话，存在有两个点 i 和 j ，如果其建边的话，最短路可能是 1 -> i -> j -> n 或者 1 -> j -> i -> n。所以我们可以跑两遍正反最短路来求。这样代表的距离也就是 dis[ i ][ 0 ] + dis[ j ][ 1 ] + 1 和 dis[ i ][ 1 ] + dis[ j ][ 0 ] + 1 了。又因为我们要取最小的，因此 dis[ i ][ 0 ] + dis[ j ][ 1 ] + 1 < dis[ i ][ 1 ] + dis[ j ][ 0 ] + 1 时，即dis[ i ][ 0 ] - dis[ i ][ 1 ] < dis[ j ][ 0 ] - dis[ j ][ 1 ]才符合最短路的条件。所以我们枚举j，然后找dis[ i ][ 0 ]的最大值，最后比较一下就可以了。
AC代码：
#include <bits/stdc++.h>
typedef long long ll;
const int maxx=200010;
const int inf=0x3f3f3f3f;
using namespace std;
struct Edge
{
int to;
int w;
int next;
} edge[maxx<<1];
struct node
{
int s1;
int s2;
int val;
bool operator<(const node&a)const
{
return val<a.val;
}
} no[maxx];
int head[maxx],cnt=0,n,m,k;
int dis[2][maxx<<1],vis[maxx],v[maxx];
void add(int u,int v,int w)
{
edge[cnt].w=w;
edge[cnt].to=v;
edge[cnt].next=head[u];
head[u]=cnt++;
}
void spfa(int a,int b,int e)
{
memset(vis,0,sizeof(vis));
dis[a][b]=0;
vis[b]=1;
queue<int>q;
q.push(b);
while(!q.empty())
{
int u=q.front();
q.pop();
vis[u]=0;
for(int i=head[u]; i!=-1; i=edge[i].next)
{
int v=edge[i].to;
int w=edge[i].w;
if(dis[a][u]+w<dis[a][v])
{
dis[a][v]=dis[a][u]+w;
if(!vis[v])
{
q.push(v);
vis[v]=1;
}
}
}
}
}
int main()
{
cin>>n>>m>>k;
memset(head,-1,sizeof(head));
memset(dis,inf,sizeof(dis));
for(int i=1; i<=k; i++)
cin>>v[i];
int x,y;
for(int i=1; i<=m; i++)
{
cin>>x>>y;
add(x,y,1);
add(y,x,1);
}
spfa(0,1,n);
spfa(1,n,1);
for(int i=1; i<=k; i++)
{
no[i].s1=dis[0][v[i]];
no[i].s2=dis[1][v[i]];
no[i].val=no[i].s1-no[i].s2;
}
sort(no+1,no+1+k);
int ans=0;
int num=no[1].s1;
for(int i=2; i<=k; i++)
{
ans=max(ans,num+no[i].s2+1);
num=max(num,no[i].s1);
}
cout<<min(dis[0][n],ans)<<endl;
return 0;
}