思路与算法

每段最多k次转车等价最短路≤k+1。每个点做BFS得到可达关系。对中间景点B，保留同时能从家到达且能到B的最高分三个A。枚举可达的B,C，再从各自三个候选中枚举A,D，检查四个景点互异并更新分数和。

正确性说明

BFS在无权图准确求最少道路数。任意合法旅程的两端候选满足上述两重可达；固定B,C与另一端D后，A至多被C、D两个编号排除，所以前三中必有一个不劣于最优A的合法替代。替换A后同理替换D，仍保持互异。因此枚举前三不会丢失最优，枚举全部B,C穷尽其余条件。

复杂度

含可达矩阵初始化，时间O(n(n+m)+9n²)，空间O(n²+n+m)。

易错点

k=0仍允许一条直达边；不能经过家以外同一景点两次作为四个目的地。分数和可达4×10^18，用有符号64位且避免较小哨兵截断。

参考代码（C++11）

#include <bits/stdc++.h>
using namespace std;

int main() {
    int n, m, k;
    cin >> n >> m >> k;
    vector<long long> s(n);
    for (int i = 1; i < n; i++)
        cin >> s[i];
    vector<vector<int>> g(n);
    while (m--) {
        int a, b;
        cin >> a >> b;
        --a;
        --b;
        g[a].push_back(b);
        g[b].push_back(a);
    }
    vector<vector<unsigned char>> reach(n, vector<unsigned char>(n));
    for (int root = 0; root < n; root++) {
        vector<int> d(n, -1), q(1, root);
        d[root] = 0;
        for (int i = 0; i < (int)q.size(); i++) {
            int u = q[i];
            reach[root][u] = 1;
            if (d[u] == k + 1)
                continue;
            for (int v : g[u])
                if (d[v] < 0) {
                    d[v] = d[u] + 1;
                    q.push_back(v);
                }
        }
    }
    vector<vector<int>> best(n);
    for (int b = 1; b < n; b++)
        for (int a = 1; a < n; a++)
            if (a != b && reach[0][a] && reach[a][b]) {
                auto &v = best[b];
                v.push_back(a);
                sort(v.begin(), v.end(), [&](int x, int y) {
                    return s[x] > s[y];
                });
                if (v.size() > 3)
                    v.pop_back();
            }
    long long ans = 0;
    for (int b = 1; b < n; b++)
        for (int c = 1; c < n; c++)
            if (b != c && reach[b][c])
                for (int a : best[b])
                    if (a != c)
                        for (int d : best[c])
                            if (d != b && d != a)
                                ans = max(ans, s[a] + s[b] + s[c] + s[d]);
    cout << ans << "\n";
}