[USACO09DEC] Cow Toll Paths G

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

按牧场过路费从小到大加入 Floyd 中转点，维护边权和最短路；每次加入新中转点后，用“边权和 + 当前允许最大点权”更新所有点对答案。

OJ: luogu

题目 ID: P2966

难度:提高+/省选-

标签:最短路Floyd图论思维

日期: 2026-06-20 04:47

目录

  1. 题意
  2. 思路
    1. 关键观察
    2. 为什么这样不会漏
  3. 代码
  4. 复杂度
  5. 总结
  6. 一图流解析

题意

有一张 N 个点的无向图，每条边有边权 L。
每个点还有一个点权 C，表示这个牧场的过路费。

从 s 走到 t 的总费用不是单纯的路径边权和，而是：

  1. 路径上所有边权之和
  2. 再加上这条路径经过的所有点里，最大的那个过路费

给你很多组查询，要求回答每组 (s,t) 的最小总费用。

思路

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

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

const int MAXN = 55;
const int MAXM = 505;
const long long INF = (1LL << 60);

struct Edge {
    int to;
    int w;
};

struct State {
    int u;
    int rank_id;
    long long edge_sum;

    bool operator < (const State &other) const {
        return edge_sum > other.edge_sum;
    }
};

int n, m, q;
int toll_fee[MAXN];
int toll_rank[MAXN];
int toll_value[MAXN];
long long dist_state[MAXN][MAXN];
vector<Edge> g[MAXN];

int prepare_ranks() {
    vector<int> vals;
    for (int i = 1; i <= n; i++) {
        vals.push_back(toll_fee[i]);
    }
    sort(vals.begin(), vals.end());
    vals.erase(unique(vals.begin(), vals.end()), vals.end());

    int cnt = (int) vals.size();
    for (int i = 1; i <= cnt; i++) {
        toll_value[i] = vals[i - 1];
    }
    for (int i = 1; i <= n; i++) {
        toll_rank[i] = lower_bound(vals.begin(), vals.end(), toll_fee[i]) - vals.begin() + 1;
    }
    return cnt;
}

long long solve_one_query(int s, int t, int rank_cnt) {
    for (int i = 1; i <= n; i++) {
        for (int j = 1; j <= rank_cnt; j++) {
            dist_state[i][j] = INF;
        }
    }

    priority_queue<State> pq;
    dist_state[s][toll_rank[s]] = 0;
    pq.push({s, toll_rank[s], 0});

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

        int u = cur.u;
        int rk = cur.rank_id;
        long long edge_sum = cur.edge_sum;

        if (edge_sum != dist_state[u][rk]) {
            continue;
        }

        for (size_t i = 0; i < g[u].size(); i++) {
            int v = g[u][i].to;
            int nr = max(rk, toll_rank[v]);
            long long nd = edge_sum + g[u][i].w;

            if (nd < dist_state[v][nr]) {
                dist_state[v][nr] = nd;
                pq.push({v, nr, nd});
            }
        }
    }

    long long ret = INF;
    for (int rk = 1; rk <= rank_cnt; rk++) {
        if (dist_state[t][rk] >= INF / 2) {
            continue;
        }
        long long total_cost = dist_state[t][rk] + toll_value[rk];
        if (total_cost < ret) {
            ret = total_cost;
        }
    }
    return ret;
}

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

    cin >> n >> m >> q;

    for (int i = 1; i <= n; i++) {
        cin >> toll_fee[i];
        g[i].clear();
    }

    for (int i = 1; i <= m; i++) {
        int u, v, len;
        cin >> u >> v >> len;
        g[u].push_back({v, len});
        g[v].push_back({u, len});
    }

    int rank_cnt = prepare_ranks();

    for (int i = 1; i <= q; i++) {
        int s, t;
        cin >> s >> t;
        cout << solve_one_query(s, t, rank_cnt) << '\n';
    }

    return 0;
}

brute.cpp 的想法很直观：

  1. 对一条具体查询 (s,t)，在状态里额外记录“当前路径上最大点权是多少”
  2. 用 Dijkstra 维护：
    • 走到某个点时的边权和
    • 同时知道当前最大点权
  3. 最后取 边权和 + 最大点权 的最小值

这个写法完全贴着题意，但如果有很多询问，就要反复跑很多次最短路。

这题真正的关键，是把“最大点权”这件事和 Floyd 结合起来。

关键观察

如果一条路径经过的所有中转点里，最大点权是 X，那么这条路径的总代价就是：

  • 边权和最短值 + X

也就是说，我们可以把问题拆成两部分：

  1. 先控制“允许哪些点作为中转点”
  2. 再在这个限制下求边权和最短路

最自然的做法是：

  1. 把所有点按过路费 C[i] 从小到大排序
  2. 依次把这些点加入 Floyd 的中转点集合
  3. 当加入到第 k 个点时，说明：
    • 当前只允许过路费不超过 C[ord[k]] 的点做中转

这时 dist[i][j] 表示的就是：

  • 中转点限制在这批点里时，i -> j 的最小边权和

于是答案就能更新成：

  • dist[i][j] + max(C[i], C[j], C[ord[k]])

这张图展示的就是这个思路：

flowchart TD
  A["按点权升序加入中转点"] --> B["Floyd 更新 dist[i][j]"]
  B --> C["当前允许的最大中转点权 = C[ord[k]]"]
  C --> D["answer[i][j] = dist[i][j] + max(C[i], C[j], C[ord[k]])"]

图里真正要看的，是“边权和”和“最大点权”被拆开处理了：
Floyd 只负责维护边权和最短路；
而当前这轮允许的最大中转点权，则由排序后的第 k 个点统一提供。

为什么这样不会漏

任意一条最优路径，都有一个“路径上最大点权”。
设这个值是 X，那么当我们枚举到所有点权 <= X 的点都已经允许做中转时：

  • 这条路径就已经在 Floyd 的考虑范围里了
  • 它对应的总代价也会在那一轮被算出来

所以把所有 k 都扫一遍，就不会漏掉真正的最优解。

代码

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

const int MAXN = 250 + 5;
const long long INF = (1LL << 60);

struct NodeOrder {
    int id;
    int toll;

    bool operator < (const NodeOrder &other) const {
        if (toll != other.toll) {
            return toll < other.toll;
        }
        return id < other.id;
    }
};

int n, m, q;
int toll_fee[MAXN];
long long dist_arr[MAXN][MAXN];
long long answer[MAXN][MAXN];
NodeOrder ord[MAXN];

void solve() {
    sort(ord + 1, ord + n + 1);

    for (int k = 1; k <= n; k++) {
        int mid = ord[k].id;

        // Floyd：只允许过路费不超过 ord[k].toll 的点做中转。
        for (int i = 1; i <= n; i++) {
            if (dist_arr[i][mid] >= INF / 2) {
                continue;
            }
            for (int j = 1; j <= n; 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;
                }
            }
        }

        // 此时 dist_arr[i][j] 表示：
        // 中转点只允许从前 k 个点里选时，i 到 j 的最短边权和。
        for (int i = 1; i <= n; i++) {
            for (int j = 1; j <= n; j++) {
                if (dist_arr[i][j] >= INF / 2) {
                    continue;
                }
                long long total_cost = dist_arr[i][j] + max(ord[k].toll, max(toll_fee[i], toll_fee[j]));
                if (total_cost < answer[i][j]) {
                    answer[i][j] = total_cost;
                }
            }
        }
    }
}

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

    cin >> n >> m >> q;

    for (int i = 1; i <= n; i++) {
        cin >> toll_fee[i];
        ord[i] = {i, toll_fee[i]};
    }

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

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

        if (len < dist_arr[u][v]) {
            dist_arr[u][v] = len;
            dist_arr[v][u] = len;
        }
    }

    solve();

    for (int i = 1; i <= q; i++) {
        int s, t;
        cin >> s >> t;
        cout << answer[s][t] << '\n';
    }

    return 0;
}

复杂度

排序是：

  • O(NlogN)O(N log N)

主过程是一次 Floyd：

  • O(N3)O(N^3)

在每一轮 k 之后，我们还要顺手更新一次所有点对答案，这也是 O(N3)O(N^3) 量级。

总复杂度：

  • O(N3)O(N^3)

空间复杂度：

  • O(N2)O(N^2)

总结

这题不是普通 Floyd，也不是普通点权最短路。

真正的核心是这个拆分：

  1. Floyd 维护“边权和最短路”
  2. 排序控制“当前路径允许的最大点权”

把“路径总代价 = 边权和 + 最大点权”拆开以后，这题就会变成一个很顺的排序 + Floyd 模型。

一图流解析

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

一图流解析