Codeforces Round #621 (Div. 1 + Div. 2).D. Cow and Fields

 1 #include<bits/stdc++.h>
 2 using namespace std;
 3 #define lson l,m,rt<<1
 4 #define rson m+1,r,rt<<1|1
 5 #define rush ios::sync_with_stdio(false);cin.tie(0);
 6 const int inf = 0x3f3f3f3f;
 7 const long long linf = 0x3f3f3f3f3f3f3f3f;
 8 int dis[200005][2];
 9 int tes[200005];
10 vector<int>g[200005];
11 int n,m,k;
12 int check[200005];
13 struct vt{
14     int X1;int Xn;
15 }s[200005];
16 bool cmp(const vt &x,const vt &y)
17 {
18     return x.X1-x.Xn<y.X1-y.Xn;
19 }
20 void bfs(int x,int st) 
21 {
22     queue<int>v;
23     v.push(x);
24     for(int i=1;i<=n;i++)check[i]=0;
25     check[x]=1;
26     while(!v.empty())
27     {
28         int temp=v.front();
29         v.pop();
30         for(auto i:g[temp])
31         {
32             if(!check[i]){
33             dis[i][st]=dis[temp][st]+1;
34             check[i]=1;
35             v.push(i);
36             }
37         }
38     }
39 }
40 int main()
41 {
42     rush
43     cin>>n>>m>>k;
44     for(int i=0;i<k;i++)
45     {
46         cin>>tes[i];
47     }
48     for(int i=0;i<m;i++){
49         int a,b;
50         cin>>a>>b;
51         g[a].push_back(b);
52         g[b].push_back(a);
53     }
54     bfs(1,0);
55     bfs(n,1);
56     for(int i=0;i<k;i++)
57     {
58         s[i].X1=dis[tes[i]][0];
59         s[i].Xn=dis[tes[i]][1];
60     }
61     sort(s,s+k,cmp);int tem=0,ans=0;
62     for(int i=0;i<k;i++)
63     {
64         if(i!=0){
65             ans=max(ans,tem+s[i].Xn+1);
66         }
67         tem=max(tem,s[i].X1);
68     }
69     cout<<min(dis[n][0],ans)<<endl;
70 }