D. Cow and Fields

Codeforces Round621 (Div. 1 + Div. 2) D. Cow and Fields

Description

Bessie is out grazing on the farm, which consists of n fields connected by m bidirectional roads. She is currently at field 1, and will return to her home at field n at the end of the day.

The Cowfederation of Barns has ordered Farmer John to install one extra bidirectional road. The farm has k special fields and he has decided to install the road between two different special fields. He may add the road between two special fields that already had a road directly connecting them.

After the road is added, Bessie will return home on the shortest path from field 1 to field n. Since Bessie needs more exercise, Farmer John must maximize the length of this shortest path. Help him!

Input
The first line contains integers n, m, and k () — the number of fields on the farm, the number of roads, and the number of special fields.

The second line contains k integers () — the special fields. All ai are distinct.

The i-th of the following m lines contains integers xi and yi (), representing a bidirectional road between fields xi and yi.

It is guaranteed that one can reach any field from every other field. It is also guaranteed that for any pair of fields there is at most one road connecting them.

Output
Output one integer, the maximum possible length of the shortest path from field 1 to n after Farmer John installs one road optimally.

Examples
input
5 5 3
1 3 5
1 2
2 3
3 4
3 5
2 4
output
3
input
5 4 2
2 4
1 2
2 3
3 4
4 5
output
3
Note
The graph for the first example is shown below. The special fields are denoted by red. It is optimal for Farmer John to add a road between fields 3 and 5, and the resulting shortest path from 1 to 5 is length 3.

The graph for the second example is shown below. Farmer John must add a road between fields 2 and 4, and the resulting shortest path from 1 to 5 is length 3.

Problem solving

这道题的意思就是给你一个图，让你在指定的点中找两个点连起来使得，连接之后的图中的最短路最小。
首先我们通过bfs计算出1和n到其他每个点的最短路长度，分别用数组a和数组b存储。连接xy两条边之后，路径1->x->y->n的长度即为。连接xy之后路径长度产生变化的路径也只有这条路，即1->x->y->n。连接之后可能这条路会变成最短路，所以我们看这条路能达到的最长的路即可.即的最大值。暴力查找的话n^2肯定会超时。
所以现在我们假设，要求的最大值并且满足。因此我们对那些特殊点根据进行排序。
然后遍历一下。用一个变量储存特殊点到1的最短距离。每次更新路径能达到的最大值。最后输出最大值和加边之前的最短路中的最小值即可。

Code

#include <bits/stdc++.h>
using namespace std;
typedef long long ll;
#define mp make_pair
#define pb push_back
#define fa(i, x, y)       for (int i = x; i <= y; i++)
#define fs(i, x, y)       for (int i = x; i >= y; i--)
const int maxn = 2e5 + 10;
const int mod = 1e9 + 10;
const int inf = 0x3f3f3f3f;
int n, m, k, u, v, a[maxn], q[maxn], d1[maxn], vis[maxn], dn[maxn];
vector<int> V[maxn];
void bfs(int s, int *d)
{
    fa(i, 1, n)       vis[i] = 0, d[i] = n + 1;
    int mid = 0;
    vis[s] = 1; d[s] = 0;
    q[mid++] = s;
    fa(i, 0, mid){
        int miu = q[i];

        for (auto miv:V[miu]) {
            if (d[miv] > d[miu] + 1) {
                d[miv] = d[miu] + 1;
                q[mid++] = miv;
            }
        }
    }
}
int main()
{
    ios::sync_with_stdio(0);
    cin >> n >> m >> k;
    fa(i, 1, k)       cin >> a[i];
    fa(i, 1, m){
        cin >> u >> v;
        V[u].pb(v); V[v].pb(u);
    }
    bfs(1, d1), bfs(n, dn);
    sort(a + 1, a + k + 1, [&](int a, int b){
        return d1[a] - dn[a] < d1[b] - dn[b];
    });//新学到的黑科技，虽然不太懂原理但是作用就是根据xi-yi进行排序。
    int ans = 0, m4a1 = d1[a[1]];//m4a1记录1到x的最短路径中的最大值
    fa(i, 2, k){
        ans = max(ans, m4a1 + dn[a[i]] + 1);//每次更新连接xy之后的最长路径
        m4a1 = max(m4a1, d1[a[i]]);
    }
    ans = min(ans, d1[n]);
    cout << ans << endl;
    return 0;
}

总结

  1. 需要对一个函数调用多次并且记录的话，可以在函数中用指针形式传数组
  2. sort那个黑科技
赏