最短路、Bellman-Ford算法,bfs广度优先搜索

题意：

Cgg正在农场放牧，该农场由n个由m条双向道路连接的田地组成。目前Cgg在1号田地，并将在一天结束时到达位于第n号田地的家。
出于对农场发展的考虑，小黄毛牛头人协会命令Cgg铺设一条额外的双向道路。 其中该农场有k个特殊田地，Cgg决定在两个不同的特殊田地之间安装道路。
注意，Cgg可以在已经连接两个特殊字段之间添加道路。（即允许创建重边）
添加道路后，Cgg将沿着从1号田地到n号田地的最短路径返回家中。 由于Cgg的牛需要更多的运动，因此Cgg必须最大限度地增加这条最短路径的长度。 帮帮他！

输入
第一行包含三个整数n,m,k (2≤n≤200000, n−1≤m≤200000, 2≤k≤n) 分别代表田地数，道路数以及特殊田地的个数。
接下来一行包含k个整数，代表特殊田地的序号。
接下来m行包含两个整数x,y表示存在x到y的双向道路。
输入保证联通，保证没有重边。

输出
输出一个数，Cgg可以得到的最短路的最大值。

样例
输入

5 5 3
1 3 5
1 2
2 3
3 4
3 5
2 4

输出
3

提示
对于样例一，可以链接3号田地与5号田地，使得最短路径为3.

分析

本题先不管是否能够做出来，我们可以很清楚的认识到这是一个求解有关最短路径的问题！！！！
我个人认为，本题实际上是考验了我们是否理解了最短路径算法的原理。如果只会像套模板一样的话。
是做不出来的。

让我们看一下最短路径算法的鼻祖，Bellman-Ford 算法：
对于起点start
d[i] 表示 start 到达第i号节点的最短路径
那么贝尔曼福德就像如果我一直更新这个式子
d[i] = min(d[i],d[j]+cost[j][i]) cost[j][i]是指一条由j到i的边的权值
因为最开始，d[start] = 0这样不停的维护，直到有一天不再需要维护了，
那么最终d就确定了，d[i]就是start到节点i的最短距离！！！
(其实我个人认为这和广度优先搜索bfs有一点相似)

那现在回到本题，我们要选择两个特殊节点在他们中间修一条路，要使得修完这条路后图的最短路径最长
首先，我说：修路前的最短路径长度 <= 修路后的最短路径长度
这是显而易见的。
我们修路后，很有可能造成影响，使得最短路径变的更短了！！
那我们想一想，造成影响，我们会对什么路径，或者说是在什么情况下会造成影响呢？？？
假设，有 a , b 两个特殊节点
我在他们中间修一条路 e。
那么我说可能比原来的最短路径小的路径，一定是通过e的！！！！对不对，如果我新添的这条路你都没有用到，那你怎么可能会小于原来的最短路径呢？就是相当于你还是在原来的图中跑。
如此，我们知道了，我们只用关注通过e的路径，就好了。看他们是否会小于原先的最短路径。
那么，现在我们看假设我们是从start到a再到b再到end的话。
这种方式的路径最短是不是start到a的最短距离再加上end到b上的最短距离这是关键
同理，如果是从start到b再到a的话，那么就是start到b的最短就离再加上end到a的最短距离。
我们只需要比较这两条路就可以了！！！！！！！！！

是不是和Bellman-Ford算法很相像？？老实说我这道题的解题思路就是受Bellman-Ford算法启发的！！！

那我们可以进行两次广度优先搜索，一次以start为起点一次以end为起点，分别记录下所有特殊节点到达
start的最短距离，以及到达end的最短距离。
如此我们在枚举，哪两个用于连接的特殊节点，和原先最短路径进行比较就好了。

等等！似乎k会很大？一一枚举k*k是过不去的！那怎么办呢？
我们再看看我们之前得出的结论：
记d[i]为start到i的最短距离、p[i]为end到i的最短距离
对于选定的特殊节点a、b我们要比较
d[a] + 1 + p[b] 与 d[b] + 1 + p[a]
但是其实我们想一想、单看d[a] + 1 + p[b]
对于选定的节点a我们和剩下的节点中的p最大的节点结合。这样我们才能最大可能地避免改变最小路径值
同样对于节点a我们考虑和剩下的d最大的结合。

如果你这么想你就错了！！！！！因为这两个古井是绑定在一起的，你把不能单独拆开来看！及具体不好说，你可以发现你连CF上的两个测试用例都过不去！！
其实上述式子就相当于：
min(d[a],d[b]) + 1 + min(p[a],p[b]) 这是 a , b两点加路后通过a,b的最短路径
固然会有 min(d[a],d[b]) = d[a] 与 min(p[a],p[b]) = p[a].但是再次提是不会影响最终答案安定的！！

有没有什么想法？
我们可以先按照d从小到大排序，这样我们从左往右遍历，只和他后面的点结合时min(d[a],d[b])就已经确定了
只要在确定min(p[a],p[b])就可以了。而这其中p[a]也已经确定了。那么我们只需a之后p最大的充当b就可以保证min(p[a],p[b])是最大的了！！！！在维护一个数组就可以啦！！！

到这里此题结束，确实是有些难度（对我而言。。。。。）

代码如下、注意细节

#include<iostream>
#include<algorithm>
#include<vector>
#include<deque>
using namespace std;
typedef pair<int, int> pii;
const int max_n = 250000;
const int inf = max_n;
int n, m, k;
int cnt1[max_n];
int cnt2[max_n];
int spec[max_n];
int speci[max_n];
int max_sum[max_n];
vector<int> G[max_n];

bool cmp1(int a, int b) {
    return cnt1[a] < cnt1[b];
}

bool cmp2(int a, int b) {
    return cnt2[a] < cnt2[b];
}

void bfs(int node,bool type = true) {
    deque<int> que;que.push_back(node);
    if (type) {
        fill(cnt1, cnt1 + max_n, inf);
        cnt1[node] =0;
        while (!que.empty()) {
            int now = que.front();que.pop_front();
            for (int i = 0;i < G[now].size();i++) {
                if (cnt1[G[now][i]] <= cnt1[now] + 1)continue;
                cnt1[G[now][i]] = cnt1[now] + 1;
                que.push_back(G[now][i]);
            }
        }
        return;
    }
    fill(cnt2, cnt2 + max_n, inf);
    cnt2[node] = 0;
    while (!que.empty()) {
        int now = que.front();que.pop_front();
        for (int i = 0;i < G[now].size();i++) {
            if (cnt2[G[now][i]] <= cnt2[now] + 1)continue;
            cnt2[G[now][i]] = cnt2[now] + 1;
            que.push_back(G[now][i]);
        }
    }
}

int main() {
    ios::sync_with_stdio(0);
    cin >> n >> m >> k;
    for (int i = 0;i < k;i++)cin >> spec[i];
    for (int i = 0;i < k;i++)speci[i] = spec[i];
    for (int i = 0;i < m;i++) {
        int x, y;cin >> x >> y;
        G[x].push_back(y);
        G[y].push_back(x);
    }
    bfs(1);int ans = cnt1[n];
    bfs(n, false);
    sort(spec, spec + k, cmp1);
    max_sum[k - 1] = cnt2[spec[k - 1]];
    for (int i = k - 2;i >= 0;i--) {
        max_sum[i] = max(max_sum[i + 1], cnt2[spec[i]]);
    }
    int camp = -1;
    for (int i = 0;i < k - 1;i++) {
        camp = max(camp, cnt1[spec[i]] + min(cnt2[spec[i]], max_sum[i + 1]) + 1);
    }
    if (camp == -1)cout << ans << endl;
    else cout << min(ans,camp) << endl;
}