题目描述

blablabla

样例

blablabla

算法1

(暴力枚举) $O(n^2)$

blablabla

时间复杂度

参考文献

C++ 代码

#include <iostream>
#include <vector>
#include <queue>
#include <cstring>
using namespace std;

const int N = 1.1e5 + 10, M = 2.5e6 + 10, INF = 0x3f3f3f3f;
int e[M], ne[M], h[N], w[M], d[N], idx;
bool v[M];
typedef pair<int, int> PII;

void add(int a, int b, int c) {
    e[idx] = b;
    w[idx] = c;
    ne[idx] = h[a];
    h[a] = idx++;
}

void dijkstra(int s, int t, int n, int k) {
    memset(d, 0x3f, sizeof d);
    memset(v, false, sizeof v);
    priority_queue<PII, vector<PII>, greater<>> heap;

    d[s] = 0;
    heap.push({0, s});
    while (!heap.empty()) {
        auto [distance, u] = heap.top();
        heap.pop();

        if (v[u]) continue;
        v[u] = true;

        for (int i = h[u]; i != -1; i = ne[i]) {
            int j = e[i];
            if (d[j] > distance + w[i]) {
                d[j] = distance + w[i];
                heap.push({d[j], j});
            }
        }
    }

    int res = INF;
    for (int i = 0; i <= k; i++) {
        res = min(res, d[t + i * n]);
    }
    cout << (res == INF ? -1 : res) << endl;
}

int main() {
    int n, m, k, s, t;
    cin >> n >> m >> k >> s >> t;

    memset(h, -1, sizeof h);
    while (m--) {
        int x, y, z;
        cin >> x >> y >> z;

        // 添加普通边
        add(x, y, z);
        add(y, x, z);

        // 分层处理：最多免费 k 次
        for (int i = 1; i <= k; i++) {
            add(x + i * n, y + i * n, z);
            add(y + i * n, x + i * n, z);
            add(x + (i - 1) * n, y + i * n, 0);
            add(y + (i - 1) * n, x + i * n, 0);
        }
    }

    dijkstra(s, t, n, k);
    return 0;
}

算法2

(暴力枚举) $O(n^2)$

blablabla

时间复杂度

参考文献

C++ 代码

blablabla