[USACO09FEB] Revamping Trails G

GitHub跳转原题关系图返回列表

把状态定义成“当前所在牧场 + 已改造道路数”。走一条边时要么正常付边权，要么消耗一次改造机会把这条边代价降成 0，在状态图上跑 Dijkstra。

OJ: luogu

题目 ID: P2939

难度:普及+/提高

标签:最短路图论堆

日期: 2026-06-20 05:04

目录

  1. 题意
  2. 思路
    1. 状态定义
  3. 代码
  4. 复杂度
  5. 总结
  6. 一图流解析

题意

给你一张无向带权图，从 1 走到 N。

你可以选择最多 K 条边，把它们“升级成高速路”，升级后的通过时间直接变成 0。

问最少需要多少时间到达终点。

思路

先看一个最直接的小数据暴力：

cpp
#include <bits/stdc++.h>
using namespace std;

const long long INF = (1LL << 60);

int n, m, k;
long long dist_arr[205][205];

int state_id(int city, int used) {
    return used * n + city;
}

int main() {
    ios::sync_with_stdio(false);
    cin.tie(nullptr);

    cin >> n >> m >> k;

    int tot = (k + 1) * n;
    for (int i = 1; i <= tot; i++) {
        for (int j = 1; j <= tot; j++) {
            if (i == j) {
                dist_arr[i][j] = 0;
            }
            else {
                dist_arr[i][j] = INF;
            }
        }
    }

    for (int i = 1; i <= m; i++) {
        int u, v, len;
        cin >> u >> v >> len;

        for (int used = 0; used <= k; used++) {
            int a = state_id(u, used);
            int b = state_id(v, used);
            if (len < dist_arr[a][b]) {
                dist_arr[a][b] = len;
                dist_arr[b][a] = len;
            }

            if (used < k) {
                a = state_id(u, used);
                b = state_id(v, used + 1);
                if (0 < dist_arr[a][b]) {
                    dist_arr[a][b] = 0;
                }

                a = state_id(v, used);
                b = state_id(u, used + 1);
                if (0 < dist_arr[a][b]) {
                    dist_arr[a][b] = 0;
                }
            }
        }
    }

    for (int mid = 1; mid <= tot; mid++) {
        for (int i = 1; i <= tot; i++) {
            if (dist_arr[i][mid] >= INF / 2) {
                continue;
            }
            for (int j = 1; j <= tot; j++) {
                if (dist_arr[mid][j] >= INF / 2) {
                    continue;
                }
                long long nd = dist_arr[i][mid] + dist_arr[mid][j];
                if (nd < dist_arr[i][j]) {
                    dist_arr[i][j] = nd;
                }
            }
        }
    }

    long long answer = INF;
    for (int used = 0; used <= k; used++) {
        if (dist_arr[state_id(1, 0)][state_id(n, used)] < answer) {
            answer = dist_arr[state_id(1, 0)][state_id(n, used)];
        }
    }

    cout << answer << '\n';

    return 0;
}

brute.cpp 会把“已经升级了多少条边”直接展开成分层图：

  • 第 0 层：还没用过改造机会
  • 第 1 层：已经用过 1 次
  • …
  • 第 K 层：已经用过 K 次

如果原图里有一条边 u <-> v，那么就有两种走法：

  1. 不改造这条边：
    • 留在当前层
    • 花费原边权
  2. 改造这条边：
    • 跳到下一层
    • 花费 0

这个思路和 P4822 非常像，只是那里“用卡后边权减半”，这里则是“改造后边权直接变 0”。

状态定义

设：

  • dist[u][used] 表示到达点 u，并且已经使用了 used 次改造机会时的最短时间

那么沿一条边走到 v 时，有两种转移：

  1. 正常走：
    • (u, used) -> (v, used)
    • 代价加 w
  2. 如果 used < K，把这条边改成高速路：
    • (u, used) -> (v, used+1)
    • 代价加 0

这张图表示的就是这个转移：

flowchart LR
  A["(u, used)"] -->|"w"| B["(v, used)"]
  A -->|"0"| C["(v, used+1)"]

图里每往下一层一次，就表示多消耗了一次改造机会。
而留在本层，则表示这条边不改造，按原来的时间走。

因为所有边权都非负，所以直接在这个状态图上跑 Dijkstra 即可。

最后答案同样不是只看用了恰好 K 次，而是：

  • dist[N][0..K] 的最小值

因为你没有义务把改造机会全部用完。

代码

cpp
#include <bits/stdc++.h>
using namespace std;

const int MAXN = 10000 + 5;
const int MAXM = 50000 * 2 + 5;
const long long INF = (1LL << 60);

struct HeapNode {
    int u;
    int used;
    long long dist;

    bool operator < (const HeapNode &other) const {
        return dist > other.dist;
    }
};

int n, m, k;
int head[MAXN], to[MAXM], nxt[MAXM], w[MAXM], edge_cnt;
long long dist_arr[MAXN][25];
bool vis[MAXN][25];

void init_graph() {
    edge_cnt = 0;
    for (int i = 1; i <= n; i++) {
        head[i] = 0;
    }
}

void add_edge(int u, int v, int len) {
    edge_cnt++;
    to[edge_cnt] = v;
    w[edge_cnt] = len;
    nxt[edge_cnt] = head[u];
    head[u] = edge_cnt;
}

void dijkstra() {
    for (int i = 1; i <= n; i++) {
        for (int j = 0; j <= k; j++) {
            dist_arr[i][j] = INF;
            vis[i][j] = false;
        }
    }

    priority_queue<HeapNode> pq;
    dist_arr[1][0] = 0;
    pq.push({1, 0, 0});

    while (!pq.empty()) {
        HeapNode cur = pq.top();
        pq.pop();

        int u = cur.u;
        int used = cur.used;
        if (vis[u][used]) {
            continue;
        }
        vis[u][used] = true;

        for (int i = head[u]; i != 0; i = nxt[i]) {
            int v = to[i];

            long long nd = dist_arr[u][used] + w[i];
            if (nd < dist_arr[v][used]) {
                dist_arr[v][used] = nd;
                pq.push({v, used, nd});
            }

            // 把这条边升级成高速路，本次通过时间直接变成 0。
            if (used < k && dist_arr[u][used] < dist_arr[v][used + 1]) {
                dist_arr[v][used + 1] = dist_arr[u][used];
                pq.push({v, used + 1, dist_arr[v][used + 1]});
            }
        }
    }
}

int main() {
    ios::sync_with_stdio(false);
    cin.tie(nullptr);

    cin >> n >> m >> k;
    init_graph();

    for (int i = 1; i <= m; i++) {
        int u, v, len;
        cin >> u >> v >> len;
        add_edge(u, v, len);
        add_edge(v, u, len);
    }

    dijkstra();

    long long answer = INF;
    for (int used = 0; used <= k; used++) {
        if (dist_arr[n][used] < answer) {
            answer = dist_arr[n][used];
        }
    }

    cout << answer << '\n';

    return 0;
}

复杂度

状态数是：

  • N(K+1)N(K+1)

每条原图边在每一层都会产生常数条转移，所以总复杂度大致为：

  • O(KMlog⁡(NK))O(KM \log (NK))

在本题范围内完全可行。

空间复杂度：

  • O(NK)O(NK)

总结

这题和“卡片减半边权”那类题本质一样，区别只在转移代价。

一旦把“已经用了多少次特殊机会”写进状态里，问题就重新变回了标准的状态最短路。

一图流解析

这张图把本题的建模、关键转移、实现检查和训练方法压缩到一页，适合读完正文后复盘。

一图流解析