Codeforces Roun d #621 (Div. 1 + Div. 2) D. Cow and Fields 最短路+贪心 图上特殊点加边使最短路最大

题目链接：https://codeforces.ml/contest/1307/problem/D
题目大意：
有一个无向图n个点m条边，其中有k个特殊点。现在让你在两个特殊点之间连一条边。让1到n的最短路最大， 并且输出这个最短路的大小。

$\begin{array}{l} dis1[i]:1到i的最短距离 \\ dis2[i]:n到i的最短距离 \\ 如果我们在i和j连边最短路可能变成：min(dis1[i]+dis2[j]+1, dis2[i]+dis1[j]+1) \\ 这里对于一个点i它和谁连并不能贪心。\\ 如果规定：dis2[i]>=dis2[j]那么i和j连边最短路只可能变成dis1[i]+dis2[j]+1。或者dis1[n]\\ 我们希望最大化：dis1[i]+dis2[j]+1。对于一个i点我们这要找到dis2[i]>=dis2[j]并且dis2[j]最大的j点。\\ 把所有特殊点的dis2[]加入容器二分就可以了。 \end{array}$dis1[i]:1到i的最短距离dis2[i]:n到i的最短距离如果我们在i和j连边最短路可能变成：min(dis1[i]+dis2[j]+1,dis2[i]+dis1[j]+1)这里对于一个点i它和谁连并不能贪心。如果规定：dis2[i]>=dis2[j]那么i和j连边最短路只可能变成dis1[i]+dis2[j]+1。或者dis1[n]我们希望最大化：dis1[i]+dis2[j]+1。对于一个i点我们这要找到dis2[i]>=dis2[j]并且dis2[j]最大的j点。把所有特殊点的dis2[]加入容器二分就可以了。​

#include<bits/stdc++.h>
#define LL long long
using namespace std;
const int maxn=2e5+5;

vector< pair<int ,int > > e[maxn];
vector<int> v, d;
int n, m;
int dis1[maxn], dis2[maxn];   //dis当前的最短路
int vis[maxn];   //是否已经求出最短路
priority_queue<pair<int, int> > q;
void dijkstra(int s, int dis[], int vis[]){
    dis[s]=0;
    q.push(make_pair(-dis[s], s));
    while(!q.empty()){
        int now=q.top().second;
        q.pop();
        if(vis[now]){
            continue;
        }
        vis[now]=1;
        for(int i=0;i<e[now].size();i++){
            int v=e[now][i].first;
            if(!vis[v]&&dis[v]>dis[now]+e[now][i].second){
                dis[v]=dis[now]+e[now][i].second;
                q.push(make_pair(-dis[v], v));
            }
        }
    }
}

int main(){

    int n, m, k, x, y;scanf("%d%d%d", &n, &m, &k);
    for(int i=1; i<=k; i++){
        scanf("%d", &x);
        v.push_back(x);
    }
    for(int i=1; i<=m; i++){
        scanf("%d%d", &x, &y);
        e[x].push_back({y, 1});
        e[y].push_back({x, 1});
    }
    memset(vis, 0, sizeof(vis));
    memset(dis1, 7, sizeof(dis1));
    dijkstra(1, dis1, vis);

    memset(vis, 0, sizeof(vis));
    memset(dis2, 7, sizeof(dis2));
    dijkstra(n, dis2, vis);
    for(int i=0; i<v.size(); i++){
        d.push_back(dis2[v[i]]);
    }
    sort(d.begin(), d.end());
    int ans=0;
    for(int i=0; i<v.size(); i++){
        vector<int>::iterator p=upper_bound(d.begin(), d.end(), dis2[v[i]]);
        p--;
        if(p==d.begin()){
            continue;
        }
        p--;
        ans=max(dis1[v[i]]+(*p)+1, ans);
    }
    printf("%d\n", min(ans, dis1[n]));

    return 0;
}