P2939 [USACO09FEB] Revamping Trails G

原题链接：P2939 [USACO09FEB] Revamping Trails G

Tag：最短路、分层图

题目描述

农夫约翰每天都会认真检查他的奶牛。 他会穿越一些编号为 \(1\) 到 \(M\) 的小径（\(1 \leq M \leq 50,000\)）， 从牧场 \(1\) 一直走到牧场 \(N\)（对于测试数据给出的路径图，这段旅程总是可能的）。 农夫约翰的农场上有 \(N\) 个牧场（\(1 \leq N \leq 10,000\)）， 它们通过双向泥土小径连接在一起。 每条小径 \(i\) 连接牧场 \(P1_i\) 和 \(P2_i\)（\(1 \leq P1_i \leq N,1 \leq P2_i \leq N\)）， 需要 \(T_i\)（\(1 \leq T_i \leq 1,000,000\)）单位时间来穿越。

他想要改造农场上的一些小径，以节省长途旅行的时间。 具体来说，他将选择 \(K\)（\(1 \leq K \leq 20\)）条小径将其改造成高速公路， 这将有效地将小径的穿越时间减少到 \(0\)。 帮助 FJ 决定改造哪些小径以最小化从牧场 \(1\) 到 \(N\) 的最终时间。

分析

分层图板子题，详情见 分层图。

代码实现

typedef pair<int,int> PII;

void IHaveNoLimitation() {
    int n, m, k;
    cin >> n >> m >> k;
    int s, t;
    s = 1,t = n;
    vector<vector<PII>> adj((k + 1) * n + 5);
    for (int i = 0; i < m; ++i) {
        int u, v, w;
        cin >> u >> v >> w;
        adj[u].push_back({v, w});
        adj[v].push_back({u, w});
        for (int j = 1; j <= k; ++j) {
            adj[(j - 1) * n + u].push_back({j * n + v, 0});
            adj[(j - 1) * n + v].push_back({j * n + u, 0});
            adj[j * n + u].push_back({j * n + v, w});
            adj[j * n + v].push_back({j * n + u, w});
        }
    }
    vector<int> dis((k + 1) * n + 5,INT_MAX), vis((k + 1) * n + 5);
    auto dijkstra = [&](int s) {
        dis[s] = 0;
        priority_queue<PII, vector<PII>, greater<PII>> pq;
        pq.push({0, s});
        while (!pq.empty()) {
            auto [w, cur] = pq.top();
            pq.pop();
            if (vis[cur]) continue;
            vis[cur] = 1;
            for (auto &nxt: adj[cur]) {
                auto &[to, val] = nxt;
                if (dis[to] > dis[cur] + val) {
                    dis[to] = dis[cur] + val;
                    pq.push({dis[to], to});
                }
            }
        }
    };
    dijkstra(s);
    int ans = INT_MAX;
    for (int i = 0; i <= k ; i++) {
        ans = min(ans,dis[i * n + t]);
    }
    cout << ans << endl;
}

日志

本页面创建于 2025/12/04 15:42