ABC369E Sightseeing Tour

原题链接：E - Sightseeing Tour

Tag：图论、最短路

题目描述

给你一张 \(N\) 个点，\(M\) 条边的无向图（可能有重边）。第 \(i\) 条边的端点是 \(U_i\) 和 \(V_i\)，长度是 \(T_i\)。

给定 \(Q\) 个询问，每个询问会给出 \(K\) 条边。对于每个询问，请求出经过这 \(K\) 条边（一定经过这 \(K\) 条边，但是也可以经过其他的边）的 \(1\) 到 \(N\) 的最短路的长度。

数据说明：

\(2 \leq N \leq 400\)
\(N-1 \leq M \leq 2 \times 10^5\)
\(1 \leq U_i < V_i \leq N\)
\(1 \leq T_i \leq 10^9\)
\(1 \leq Q \leq 3000\)
\(1 \leq K_i \leq 5\)
\(1 \leq B_{i,1} < B_{i,2} < \cdots < B_{i,K_i} \leq M\)
图保证连通

分析

读题发现这道题需要我们多次查询点与点之间的最短路，又发现 \(N \leq 400\) 于是我们可以跑一个 \(\text{Floyd}\) 来解决多次用到最短路这一问题。

之后就是关于经过指定的若干条边，因为数据范围同样很小，我们可以直接全排列暴力去算，这样每次查询的复杂度是 \(O(K_i!)\) 的。

还有一个问题，题目规定的是必须要经过那些边，并没有规定每一条边具体要从哪一侧走到哪一侧，因此我们还需要枚举每一条边走的方向。

上述做法的时间复杂度为 \(O(n^3 + q\times 2^{K_i} \times K_i!)\)。

代码实现

const int N = 505;
int mp[N][N];
void NeverSayNever() {
    struct edge {
        int u, v, w;
    };
    int n, m;
    cin >> n >> m;
    for (int i = 1; i <= n; ++i) {
        for (int j = 1; j <= n; ++j) {
            if (i == j) mp[i][j] = 0;
            mp[i][j] = LLONG_MAX;
        }
    }
    vector<edge> E(n + 1);
    for (int i = 1; i <= m; ++i) {
        int u, v, w;
        cin >> u >> v >> w;
        E.push_back({u,v,w});
        if (mp[u][v] > w) {
            mp[u][v] = mp[v][u] = w;
        }
    }
    auto Floyd = [&]() {
        for (int k = 1; k <= n; ++k) {
            for (int i = 1; i <= n; ++i) {
                for (int j = 1; j <= n; ++j) {
                    if (mp[i][j] > mp[i][k] + mp[k][j] && mp[i][k] != LLONG_MAX && mp[k][j] != LLONG_MAX) {
                        mp[i][j] = mp[i][k] + mp[k][j];
                    }
                }
            }
        }
    };
    Floyd();
    int q;
    cin >> q;
    vector<int> query(5);
    while (q--) {
        int k;
        cin >> k;
        for (int i = 0; i < k; ++i) {
            cin >> query[i];
        }
        std::sort(query.begin(), query.begin() + k);
        int ans = LLONG_MAX;
        for (int i = 0; i <= (1 << k) - 1; ++i) {
            do {
                int lst = 1, cur = 0;
                for (int j = 0; j < k; ++j) {
                    auto [u, v, w] = E[query[j]];
                    if (i >> j & 1) swap(u, v);
                    cur += mp[lst][u] + w;
                    lst = v;
                }
                ans = min(ans, cur + mp[lst][n]);
            } while (next_permutation(query.begin(), query.begin() + k));
        }
        cout << ans << endl;
    }
}

日志

本页面创建于 2024/09/20 21:20