P4568 [JLOI2011] 飞行路线

​

P4568 [JLOI2011] 飞行路线

对于从上到下的每一层的图相当于都是经过了一次免费航班

#include <iostream>
#include <algorithm>
#include <cstring>
#include <queue>

using namespace std;

#define x first
#define y second

typedef pair<int, int> PII;
const int N = 12 * (int) 1e4 + 10, M = 144 * (int) 1e5 + 10;

int n, m, k, s, t;
int head[N], edge_end[M], next_edge[M], w[M], edge_index;
bool vis[N];
int d[N];

void add(int ver1, int ver2, int val) {
   
    edge_end[edge_index] = ver2, next_edge[edge_index] = head[ver1], w[edge_index] = val, head[ver1] = edge_index++;
}

void dijkstra() {
   
    priority_queue<PII, vector<PII>, greater<PII>> queue;
    memset(d, 0x3f, sizeof d);
    d[s] = 0;
    queue.push({
   0, s});

    while (!queue.empty()) {
   
        auto [dis, u] = queue.top();
        queue.pop();

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

        for (int i = head[u]; ~i; i = next_edge[i]) {
   
            int ver = edge_end[i];
            if (d[u] + w[i] < d[ver]) {
   
                d[ver] = d[u] + w[i];
                queue.push({
   d[ver], ver});
            }
        }
    }
}

int main() {
   
    ios::sync_with_stdio(false);
    cin.tie(0), cout.tie(0);

    memset(head, -1, sizeof head);
    cin >> n >> m >> k >> s >> t;
    for (int i = 0; i < m; ++i) {
   
        int u, v, w;
        cin >> u >> v >> w;
        add(u, v, w);
        add(v, u, w);

        // 一共k + 1层图
        for (int j = 1; j <= k; ++j) {
   
            add(j * n + u, j * n + v, w);
            add(j * n + v, j * n + u, w);
            // 建立上一层到当前层的边
            add((j - 1) * n + u, j * n + v, 0);
            add((j - 1) * n + v, j * n + u, 0);
        }
    }

    for (int i = 0; i < k; ++i) add(i * n + t, (i + 1) * n + t, 0);

    dijkstra();

    cout << d[k * n + t] << "\n";
    return 0;
}

因为层与层之间也会连边, 因此需要$2M\ast k+k\times M$条边

为什么需要将每一层的终点向下一层连边?

为了保证终点之间是免费到达的, 防止上一层无法到达下一层, 也就失去了免费航班的机会