题目链接
题目大意
一辆卡车从起点s到终点t，走的是最短路径。强盗从r出发前往卡车途经的某个点拦截，同样，强盗选择最近的点。卡车走的最短路径可能有多条，求最坏情况下强盗花费的时间。
简而言之，两个步骤：
1）求r点到（所有s到t的）最短路的最短距离；
2）在这些最短距离中找最大值。
这样子，本问题即最小值最大化问题，与上一篇的思路是类似的。
解决本题，主要有两个部分：
1）求r点到其他各点的最短距离；
2）二分法找出最大值。
第二点的具体思路：二分法跑s和t之间的最短路，如果发现某点v到r的最短距离distr[v]小于等于mid，那么就不把v点加入松弛队列。
现做出下列解释：
首先，我们已经求得r到其他各点的最短距离distr，并先对s，f跑一次最短路，得到s到f的最短路径为ans。
接下来是二分，如图所示，假设s到f有5条最短路径，由于最多有n个点，所以答案的范围是0到n，现在对0到n二分。
我们可以简单地把这个过程比做是猜数字。
一开始，B心里默念了一个数字：5，然后让A来猜，范围是0到6。
A：我猜这个数字是3
B：小了
于是A知道这个数一定在4和6之间。
类比过来，一开始我们猜mid = 3；但是此时是大了还是小了，需要我们自己判断，如何判断呢？只需要对s到f跑一次最短路，当distr[v]<=mid时，不把v加入松弛队列，于是这一次v1、v2、v3都不会加入松弛队列，但是由于经过v4、v5的路也是最短路，所以求得的s到f的最短路dist[f]仍然等于ans，如此一来，我们知道存在比mid还大的答案，亦即mid偏小了，于是令left=mid+1，继续二分；
这一次，A说：我猜这个数是5；
B卖了个关子：这次不偏小
不偏小，则可能刚刚好猜中了，或者是偏大了，说明答案应该是小于等于5，所以区间缩小到4和5之间。
同样的，令mid = （4+6）/2 = 5；则此次对v1到v5都不进行松弛，结果求得dist[f] >ans，此时说明mid刚刚好或者是太大了，所以令right=mid，继续二分。
如此类推，直到区间大小缩小到1为止。
具体代码实现如下：
#include<iostream>
#include<vector>
#include<cstdio>
#include<cstring>
#include<deque>
using namespace std;
const int MAXN = 100010;
vector<int> g[MAXN];
int dist[MAXN];
int inq[MAXN];
int distr[MAXN];
int mid = 0;
//求最短距离中的最大值
//通过SPFA(r, t)，已经求得了r到其他各点的最短距离，现在要求的是最大值
//可以枚举0到n，看看哪个是符合要求的最大值，本例用二分法来查找
//现在假设最大值是mid，对于v，假设r到v的最短距离小于mid，则不对v进行松弛操作，看看s到r的最短距离是否受到影响。
//如果mid偏小，则dist[r]应该等于ans（mid右侧还有最短路），则扩大mid（即lf = mid+1），以求得最大值
//如果受到影响，则说明mid右侧没有最短路了，需要收敛一点
int SPFA(int s, int t)
{
for (int i = 0; i < MAXN; i++)
dist[i] = MAXN;
memset(inq, 0, sizeof(inq));
deque<int> q;
q.push_back(s);
dist[s] = 0;
inq[s] = true;
if (distr[s] <= mid) //如果r到s的最短距离小于等于mid，则直接到s点拦截，此时mid偏大了。
return MAXN;
while (!q.empty())
{
int u = q.front();
q.pop_front();
inq[u] = false;
for (int i = 0; i < g[u].size(); i++)
{
int v = g[u][i];
if (distr[v] <= mid) continue; //r到v的最短距离<=mid，不进行松弛操作
if (dist[v] > dist[u] + 1)
{
dist[v] = dist[u] + 1;
if (!inq[v])
{
inq[v] = true;
if (!q.empty() && dist[v] <= dist[q.front()])
q.push_front(v);
else
q.push_back(v);
}
}
}
}
return dist[t];
}
int main()
{
int n, m;
cin>>n>>m;
for (int i = 0; i < m; i++)
{
int u, v;
cin>>u>>v;
g[u].push_back(v);
g[v].push_back(u);
}
int s, t, r;
cin>>s>>t>>r;
for (int i = 0; i < MAXN; i++)
distr[i] = MAXN;
SPFA(r, s);
for (int i = 1; i <= n; i++)
distr[i] = dist[i]; //distr表示r到其他点的最短距离
int ans = SPFA(s, t);
if (ans == MAXN)
{
cout<<"0"<<endl;
return 0;
}
int lf = 0, rt = n; //一共n个点，则答案必然在0和n之间，下面用二分法查找
while (lf < rt)
{
mid = (lf + rt) / 2;
int res = SPFA(s, t);
if (res == ans)
lf = mid + 1; //s到t的最短距离没有变化，说明所求的点在右边
else
rt = mid;
}
cout<<lf<<endl;
return 0;
}