这题不是最短路求和，而是最小化路径上的最大边权；点数只有 300，可以直接用 Floyd 的 min-max 转移求所有点对的最小瓶颈路。
OJ: luogu
题目 ID: P2888
难度:普及/提高-
标签:最短路图论Floyd
日期: 2026-06-20 03:33
题意
给一张有向图。
每条边有一个栏高 H。
对每个询问 A -> B，要找一条从 A 到 B 的路径，使得：
- 路径上最高的栏尽量低
也就是把一条路径的代价定义成：
- 路径上所有边权的最大值
要求这个最大值最小。
如果从 A 不能到 B，输出 -1。
思路
先看一个最直接的小数据暴力：
// brute.cpp：对每个询问单独跑一次“最小化最大边权”的 Dijkstra。
// 只适合小数据，但很适合帮助理解瓶颈路定义并做对拍。
#include <bits/stdc++.h>
using namespace std;
const int MAXN = 105;
const int MAXM = 4005;
const int INF = 1e9;
struct HeapNode {
int u;
int cost;
bool operator < (const HeapNode &other) const {
return cost > other.cost;
}
};
int n, m, t;
int head[MAXN], to[MAXM], nxt[MAXM], w[MAXM], edge_cnt;
int dist_arr[MAXN];
bool vis[MAXN];
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;
}
// dist[v] 表示：从 start 到 v 的所有路径里，
// “路径上最大边权”这个值的最小可能值。
void dijkstra_minimax(int start) {
for (int i = 1; i <= n; i++) {
dist_arr[i] = INF;
vis[i] = false;
}
priority_queue<HeapNode> pq;
dist_arr[start] = 0;
pq.push({start, 0});
while (!pq.empty()) {
HeapNode cur = pq.top();
pq.pop();
int u = cur.u;
if (vis[u]) {
continue;
}
vis[u] = true;
for (int i = head[u]; i != 0; i = nxt[i]) {
int v = to[i];
int nd = max(dist_arr[u], w[i]);
if (nd < dist_arr[v]) {
dist_arr[v] = nd;
pq.push({v, nd});
}
}
}
}
int main() {
ios::sync_with_stdio(false);
cin.tie(nullptr);
cin >> n >> m >> t;
for (int i = 1; i <= n; i++) {
head[i] = 0;
}
edge_cnt = 0;
for (int i = 1; i <= m; i++) {
int u, v, h;
cin >> u >> v >> h;
add_edge(u, v, h);
}
while (t--) {
int a, b;
cin >> a >> b;
dijkstra_minimax(a);
if (dist_arr[b] == INF) {
cout << -1 << '\n';
}
else {
cout << dist_arr[b] << '\n';
}
}
return 0;
}暴力做法对每个询问都单独跑一次“瓶颈版 Dijkstra”：
dist[v]不再表示边权和- 而是表示从起点到
v的路径里，“最大边权”的最小可能值
这个写法很适合帮助理解题意，但这题数据里：
N <= 300T <= 40000
如果每个询问都单独做一次，还是太重复了。
这题真正的关键，是把普通 Floyd 的转移改掉。
普通最短路 Floyd 是：
dist[i][j] = min(dist[i][j], dist[i][k] + dist[k][j])
而这题里，一条路径的代价不是加法，而是：
- 路径上最大的边权
所以如果 i -> j 经过 k，那么这条路径的代价应该是：
max(dist[i][k], dist[k][j])
因为前半段和后半段各自都有一个“最大边权”，整条路径的最大边权就是两者取最大。
于是转移就变成：
dist[i][j] = min(dist[i][j], max(dist[i][k], dist[k][j]))
这就是这题的核心。
初始化时：
dist[i][j]表示直接从i到j的栏高- 如果没有边，就是
INF - 如果有重边，保留更小的栏高
Floyd 做完后，dist[A][B] 就是：
- 从
A到B的所有路径中 - “路径上最大边权”的最小值
代码
#include <bits/stdc++.h>
using namespace std;
const int MAXN = 300 + 5;
const int INF = 1e9;
int n, m, t;
int dist_arr[MAXN][MAXN];
int main() {
ios::sync_with_stdio(false);
cin.tie(nullptr);
cin >> n >> m >> t;
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;
}
}
}
for (int i = 1; i <= m; i++) {
int u, v, h;
cin >> u >> v >> h;
if (h < dist_arr[u][v]) {
dist_arr[u][v] = h;
}
}
// Floyd 的“最短路加法”改成“瓶颈路转移”：
// 经过 k 的路径代价 = max(i->k 路上最大边, k->j 路上最大边)
// 我们希望这个值尽量小，所以再对它取 min。
for (int k = 1; k <= n; k++) {
for (int i = 1; i <= n; i++) {
for (int j = 1; j <= n; j++) {
int through_k = max(dist_arr[i][k], dist_arr[k][j]);
if (through_k < dist_arr[i][j]) {
dist_arr[i][j] = through_k;
}
}
}
}
while (t--) {
int a, b;
cin >> a >> b;
if (dist_arr[a][b] == INF) {
cout << -1 << '\n';
}
else {
cout << dist_arr[a][b] << '\n';
}
}
return 0;
}复杂度
Floyd：
回答所有询问：
总复杂度：
在 N <= 300 时完全可行。
空间复杂度：
总结
这题最值得记住的是：
- Floyd 不一定只能处理“边权和最短”
只要你能定义清楚“经过中转点 k 时，路径代价如何由两段路径合成”，就可以改写转移。
这题的合成方式就是：
- 两段路径取
max - 多种方案取
min
所以本质上是一道 Floyd 版的最小瓶颈路题。
一图流解析
这张图把本题的建模、关键转移、实现检查和训练方法压缩到一页，适合读完正文后复盘。
