ac

#include <bits/stdc++.h> #define ll long long using namespace std; const int N = 2e3 + 505; ll n, m, k, val[N], dis[N][N]; bool vis[N]; vector<int> e[N]; void bfs(int start) { queue<int> q; dis[start][start] = 0; memset(vis, 0, sizeof(vis)); q.push(start); vis[start] = 1; while (q.size()) { int u = q.front(); q.pop(); for (auto v : e[u]) { if (!vis[v]) { vis[v] = 1; dis[start][v] = min(dis[start][v], dis[start][u] + 1); q.push(v); } } } } int main() { ios::sync_with_stdio(false); cin.tie(0); memset(dis, 0x3f, sizeof(dis)); cin >> n >> m >> k; for (int i = 2; i <= n; i++) cin >> val[i]; while (m--) { int u, v; cin >> u >> v; e[u].push_back(v), e[v].push_back(u); } for (int i = 1; i <= n; i++) bfs(i); k++; ll ans = 0; for (int a = 2; a <= n; a++) { if (dis[1][a] > k) continue; for (int b = 2; b <= n; b++) { if (dis[a][b] > k || b == a) continue; for (int c = 2; c <= n; c++) { if (dis[b][c] > k || c == b || c == a) continue; for (int d = 2; d <= n; d++) { if (dis[1][d] > k || dis[c][d] > k || d == b || d == c || d == a) continue; ans = max(ans, val[a] + val[b] + val[c] + val[d]); } } } } cout << ans; return 0; }

部分分做法

首先我们可以利用 BFS 在 $O(nm)$ 的时间内预处理出任意两点之间的最短路。

接下来只需要枚举四个点求解即可。题目所说的最多转车 $k$ 次，其实就是两点之间的最短路不能超过 $k+1$

#include <bits/stdc++.h>
#define ll long long
using namespace std;
const int N = 2e3 + 505;
ll n, m, k, val[N], dis[N][N];
bool vis[N];
vector<int> e[N];
void bfs(int start)
{
    queue<int> q;
    dis[start][start] = 0;
    memset(vis, 0, sizeof(vis));
    q.push(start);
    vis[start] = 1;
    while (q.size())
    {
        int u = q.front();
        q.pop();
        for (auto v : e[u])
        {
            if (!vis[v])
            {
                vis[v] = 1;
                dis[start][v] = min(dis[start][v], dis[start][u] + 1);
                q.push(v);
            }
        }
    }
}
int main()
{
    ios::sync_with_stdio(false);
    cin.tie(0);
    memset(dis, 0x3f, sizeof(dis));
    cin >> n >> m >> k;
    for (int i = 2; i <= n; i++) cin >> val[i];
    while (m--)
    {
        int u, v;
        cin >> u >> v;
        e[u].push_back(v), e[v].push_back(u);
    }
    for (int i = 1; i <= n; i++) bfs(i);
    k++;
    ll ans = 0;
    for (int a = 2; a <= n; a++)
    {
        if (dis[1][a] > k) continue;
        for (int b = 2; b <= n; b++)
        {
            if (dis[a][b] > k || b == a) continue;
            for (int c = 2; c <= n; c++)
            {
                if (dis[b][c] > k || c == b || c == a) continue;
                for (int d = 2; d <= n; d++)
                {
                    if (dis[1][d] > k || dis[c][d] > k || d == b || d == c || d == a) continue;
                    ans = max(ans, val[a] + val[b] + val[c] + val[d]);
                }
            }
        }
    }
    cout << ans;
    return 0;
}

满分做法

耗费时间的地方主要在于我们需要枚举四个点，使得时间复杂度达到了 $O(n^4)$

根据数据范围 $n\leq 2500$ 可以看出应该是枚举两个点的做法，那就值得我们思考了，因为我们计算答案肯定是要知道四个点是谁的，即我们能否通过只枚举两个点，就可以确定出另外两个点的一个可选集合，且这个可选集合的范围很小，那就可以快速求出答案了。

这里我们尝试枚举中间两个点 $b,c$ 当我们枚举了 $b$ 以后，离 $b$ 距离不超过 $k + 1$ 的点可能有若干个，因为最后我们要选取的就是在距离满足的条件下权值尽量大的点，这启发我们只需要对每个点预处理在合法范围情况下，权值较大的前三个点即可，为何是前三个点？因为枚举了一个点，有可能剩余两个点是和 $c,d$ 相同的，所以我们需要第三大的点。

这样一来枚举了 $b,c$ 以后，只需要枚举它们两前三大权值的点的情况，时间复杂度的计算来到了 $9*n^2$ 可以通过本题。

接下来就需要我们在预处理 BFS 的同时存储好离每个点权值最大的三个点。

在存储时，我们要保证该点首先离我们的起点距离小于等于 $k+1$，其次由于我们加进去的点集是属于 $a,d$ 的那么就还得保证这几个点距离 $1$ 的距离也小于等于 $k+1$ 同时不要加和起点，$1$ 号点相同的点，因为题目最终选择的景点都是不同的点。

#include <bits/stdc++.h>
#define ll long long
using namespace std;
const int N = 2e3 + 505;
ll n, m, k, val[N], dis[N][N];
bool vis[N];
vector<int> e[N];
vector<int> f[N];
bool cmp(int x, int y)
{
    return val[x] > val[y];
}
void bfs(int start)
{
    queue<int> q;
    dis[start][start] = 0;
    q.push(start);
    while (q.size())
    {
        int u = q.front();
        q.pop();
        if (start != u && start != 1 && u != 1 && dis[start][u] <= k && dis[1][u] <= k)
        //start和u都不是1，且不相等，由于我们加入的点集是a,d的集合，这些点必须1到它们距离小于等于k，且start到u小于等于k
        {
            f[start].push_back(u);
            sort(f[start].begin(), f[start].end(), cmp);
            if (f[start].size() > 3)
            {
                f[start].pop_back();
            }
        }
        for (auto v : e[u])
        {
            if (dis[start][v] > dis[start][u] + 1)
            {
                dis[start][v] = dis[start][u] + 1;
                q.push(v);
            }
        }
    }
}
int main()
{
    ios::sync_with_stdio(false);
    cin.tie(0);
    memset(dis, 0x3f, sizeof(dis));
    cin >> n >> m >> k;
    k++;
    for (int i = 2; i <= n; i++) cin >> val[i];
    while (m--)
    {
        int u, v;
        cin >> u >> v;
        e[u].push_back(v), e[v].push_back(u);
    }
    for (int i = 1; i <= n; i++) bfs(i);
    ll ans = 0;
    for (int b = 2; b <= n; b++)
    {
        for (int c = 2; c <= n; c++)
        {
            if (c == b || dis[b][c] > k) continue;
            for (auto a : f[b])
            {
                for (auto d : f[c])
                {
                    if (a == d || a == c || b == d || dis[1][a] > k || dis[a][b] > k || dis[c][d] > k || dis[d][1] > k) continue;
                    ans = max(ans, val[a] + val[b] + val[c] + val[d]); 
                }
            }
        }
    }
    cout << ans;
    return 0;
}