P4822 [BJWC2012] 冻结

P4822 [BJWC2012] 冻结

建立分层图, 第$i$层到$i+1$层代表一种优惠决策, 一共$k$层图

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

using namespace std;

typedef pair<double, int> PDI;
const int N = 30010, M = 300010;
const int INF = 0x3f3f3f3f;

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

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

void dijkstra() {
   
    priority_queue<PDI, vector<PDI>, greater<PDI>> queue;
    for (int i = 0; i < N; ++i) d[i] = INF;
    d[1] = 0;
    queue.push({
   0, 1});

    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;

    for (int i = 0; i < m; ++i) {
   
        int u, v, w;
        cin >> u >> v >> w;
        add(u, v, w);
        add(v, u, w);

        for (int j = 1; j <= k; ++j) {
   
            // 创建第k层图
            add(j * n + u, j * n + v, w);
            add(j * n + v, j * n + u, w);
            // 每层图之间的边权是半价
            double val = w / 2.0;
            add((j - 1) * n + u, j * n + v, val);
            add((j - 1) * n + v, j * n + u, val);
        }
    }

    // 连接每一层的终点位置
    for (int i = 0; i < n; ++i) add(i * n + n, (i + 1) * n + n, 0);

    dijkstra();

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