D. Cow and Fields

对于每个点 我们可以通过两次bfs求出 他离1最近的距离和离n最近的距离
对于连边就是 让d1[i]+d2[j]+1去更新最短路
我们要让d1[i]+d2[j]+1最大
我们先直接sort出来 发现第二个样例都过不了 原来是d1[i]+d2[j]可能在一条线上
我们如何才让d1[i]+d2[j]一定是i离1最近 j离n最近
我们直接按d1[i]进行排序
这样我们d1[i]的右边一定是离1更远的（要是d1值一样 但肯定不在一条链上 所以也是合法的）
所以我们直接求出一个后缀max关于d2的
然后扫一遍就可以了

int n,m,k,a[N];
vector<int>g[N];
void bfs(int u,int d1[]){
    queue<int>q;
    q.push(u);
    d1[u]=0;
    while(q.size()){
        auto t=q.front();
        q.pop();
        for(auto v:g[t]){
            if(!d1[v]&&v!=u){
                d1[v]=d1[t]+1;
                q.push(v);
            }
        }
    }
}
void solve(){
    cin>>n>>m>>k;
    int d1[N]={0},d2[N]={0};
    for(int i=1;i<=k;i++){
        cin>>a[i];
    }
    for(int i=1;i<=m;i++){
        int a,b;cin>>a>>b;
        g[a].push_back(b);
        g[b].push_back(a);
    }
    bfs(n,d1);
    bfs(1,d2);
    vector<pair<int,int>>v1;
    for(int i=1;i<=k;i++){
        v1.push_back({d1[a[i]],d2[a[i]]});
    }
    sort(all(v1));
    vector<int>mx(k+1);
    for(int i=k-1;i>=0;i--)
        mx[i]=max(mx[i+1],v1[i].second);
    int ans=-INF;
    for(int i=0;i<k-1;i++)
        ans=max(ans,mx[i+1]+v1[i].first);
    cout<<min(d1[1],ans+1)<<endl;
}

原文地址：http://www.cnblogs.com/ycllz/p/16920598.html