Codeforces 1307D - Cow and Fields【最短路+思維轉換】

題目：

  給出一個 n n n 個點， m m m 條邊的無向連通圖，其中有 k k k 個特殊的點。選擇連接配接這 k k k 個點中的兩個，使得從 1 1 1 号點到 n n n 号的最短距離最大化，并求出該最短距離。

思路：

  先考慮暴力的做法，用兩次 b f s bfs bfs 求出 1 1 1 号點和 n n n 号點到各個點的距離，分别用 x [ i ] x[i] x[i] 和 y [ i ] y[i] y[i] 表示。然後暴力枚舉這 k k k 個點中的兩個點連接配接，求出最短路的最大值，和原最短距離比較。

複雜度： O ( n 2 ) O(n^2) O(n2)

  優化：假設選擇 a a a 和 b b b 點，那麼此時的答案為 m i n ( x [ a ] + y [ b ] + 1 , x [ b ] + y [ a ] + 1 ) min(x[a]+y[b]+1,x[b]+y[a]+1) min(x[a]+y[b]+1,x[b]+y[a]+1)。假設有 x [ a ] + y [ b ] + 1 ≤ x [ b ] + y [ a ] + 1 x[a]+y[b]+1\leq x[b]+y[a]+1 x[a]+y[b]+1≤x[b]+y[a]+1，對其進行移項化簡，有： x [ a ] − y [ a ] ≤ x [ b ] − y [ b ] x[a]-y[a] \leq x[b]-y[b] x[a]−y[a]≤x[b]−y[b] 成立。是以，可以把這k個點的x[i]-y[i]進行排序，然後進行周遊。對目前周遊節點而言，其前面的所有節點和此節點均滿足上述不等式的關系。即說明，此節點和前面的節點之間連邊均可形成最短路。那麼，要做的隻是維護字首的最大 x [ i ] x[i] x[i]，以此來維護增邊後的最短路的最大值即可。最後，和原最短路值比較，較小值即為答案。

複雜度： O ( n l o g n + m ) 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;
}