Codeforces 1307D - Cow and Fields【最短路+思维转换】

题目：

  给出一个 $n$n 个点， $m$m 条边的无向连通图，其中有 $k$k 个特殊的点。选择连接这 $k$k 个点中的两个，使得从 $1$1 号点到 $n$n 号的最短距离最大化，并求出该最短距离。

思路：

  先考虑暴力的做法，用两次 $bfs$bfs 求出 $1$1 号点和 $n$n 号点到各个点的距离，分别用 $x\left[i\right]$x[i] 和 $y\left[i\right]$y[i] 表示。然后暴力枚举这 $k$k 个点中的两个点连接，求出最短路的最大值，和原最短距离比较。
复杂度： $O\left(n^2\right)$O(n2)
  优化：假设选择 $a$a 和 $b$b 点，那么此时的答案为 $min\left(x\right[a]+y[b]+1,x[b]+y[a]+1)$min(x[a]+y[b]+1,x[b]+y[a]+1)。假设有 $x\left[a\right]+y\left[b\right]+1\le x\left[b\right]+y\left[a\right]+1$x[a]+y[b]+1≤x[b]+y[a]+1，对其进行移项化简，有： $x\left[a\right]-y\left[a\right]\le x\left[b\right]-y\left[b\right]$x[a]−y[a]≤x[b]−y[b] 成立。因此，可以把这k个点的x[i]-y[i]进行排序，然后进行遍历。对当前遍历节点而言，其前面的所有节点和此节点均满足上述不等式的关系。即说明，此节点和前面的节点之间连边均可形成最短路。那么，要做的只是维护前缀的最大 $x\left[i\right]$x[i]，以此来维护增边后的最短路的最大值即可。最后，和原最短路值比较，较小值即为答案。
复杂度： $O(nlogn+m)$O(nlogn+m)

代码：

#include <bits/stdc++.h>
using namespace std;
const int N=2e5+5;
const int inf=0x3f3f3f3f;
typedef pair<int,int> P;
P d[N];
int a[N],x[N],y[N];
vector<int>pic[N];
queue<int>que;
int n;
bool vis[N];
void bfs(int s,int dis[])
{
    while(!que.empty())
        que.pop();
    fill(dis,dis+1+n,inf);
    fill(vis,vis+1+n,false);
    que.push(s);
    vis[s]=1;
    dis[s]=0;
    while(!que.empty())
    {
        int now=que.front();
        que.pop();
        for(int i=0;i<pic[now].size();i++)
        {
            int t=pic[now][i];
            if(!vis[t])
            {
                vis[t]=1;
                dis[t]=dis[now]+1;
                que.push(t);
            }
        }
    }
}
int main()
{
    int m,k,u,v;
    scanf("%d%d%d",&n,&m,&k);
    for(int i=1;i<=k;i++)
        scanf("%d",&a[i]);
    for(int i=1;i<=m;i++)
    {
        scanf("%d%d",&u,&v);
        pic[u].push_back(v);
        pic[v].push_back(u);
    }
    bfs(1,x);
    bfs(n,y);
    for(int i=1;i<=k;i++)
    {
        d[i].first=x[a[i]]-y[a[i]];
        d[i].second=a[i];
    }
    sort(d+1,d+1+k);
    int maxn=-inf,ans=0;
    for(int i=1;i<=k;i++)
    {
        int t=d[i].second;
        ans=max(ans,maxn+y[t]);
        maxn=max(maxn,x[t]);
    }
    printf("%d\n",min(ans+1,x[n]));
    return 0;
}