二分最大付费边长度，把超过阈值的边计为 1，用 0-1 BFS 判断免费额度是否足够。
OJ: luogu
题目 ID: P1948
难度:普及+/提高
标签:二分答案最短路0-1 BFS图论
日期: 2026-06-22 21:58
题意
要从 1 号电话杆连到 n 号电话杆。电信公司可以免费提供最多 k 条电话线。
剩余需要付费的电话线，其费用由其中最长的一条决定。要求最小化这条最长付费电话线的长度；如果无法连通，输出 -1。
思路
先看一个可以直接验证想法的朴素解：
cpp
#include <bits/stdc++.h>
using namespace std;
// brute.cpp：按“已经免费使用几条边”做 Dijkstra，适合小数据对拍。
const int MAXN = 105;
const int MAXP = 1005;
const int INF = 1000000000;
struct State {
int cost, node, free_used;
};
struct CmpState {
bool operator()(const State &a, const State &b) const {
return a.cost > b.cost;
}
};
int n, p, k;
int head[MAXN], to[MAXP * 2], weight_edge[MAXP * 2], nxt[MAXP * 2], edge_cnt;
int dist_value[MAXN][MAXN]; // dist_value[u][c]：到 u，已免费 c 条边时的最小最大付费边。
void add_edge(int u, int v, int w) {
edge_cnt++;
to[edge_cnt] = v;
weight_edge[edge_cnt] = w;
nxt[edge_cnt] = head[u];
head[u] = edge_cnt;
}
void read_input() {
cin >> n >> p >> k;
for (int i = 1; i <= p; i++) {
int a, b, l;
cin >> a >> b >> l;
add_edge(a, b, l);
add_edge(b, a, l);
}
}
int dijkstra() {
for (int i = 1; i <= n; i++) {
for (int j = 0; j <= k; j++) {
dist_value[i][j] = INF;
}
}
priority_queue<State, vector<State>, CmpState> pq;
dist_value[1][0] = 0;
pq.push({0, 1, 0});
while (!pq.empty()) {
State cur = pq.top();
pq.pop();
if (cur.cost != dist_value[cur.node][cur.free_used]) {
continue;
}
for (int i = head[cur.node]; i != 0; i = nxt[i]) {
int v = to[i];
int w = weight_edge[i];
int pay_cost = max(cur.cost, w);
if (pay_cost < dist_value[v][cur.free_used]) {
dist_value[v][cur.free_used] = pay_cost;
pq.push({pay_cost, v, cur.free_used});
}
if (cur.free_used < k && cur.cost < dist_value[v][cur.free_used + 1]) {
dist_value[v][cur.free_used + 1] = cur.cost;
pq.push({cur.cost, v, cur.free_used + 1});
}
}
}
int answer = INF;
for (int i = 0; i <= k; i++) {
answer = min(answer, dist_value[n][i]);
}
if (answer == INF) {
return -1;
}
return answer;
}
int main() {
ios::sync_with_stdio(false);
cin.tie(nullptr);
read_input();
cout << dijkstra() << '\n';
return 0;
}暴力状态可以记录“到哪个点、已经免费了几条边”，再求付费边最大值的最小可能。这个方法适合验证，但正解可以利用单调性。
二分答案 x，表示希望所有付费边长度都不超过 x。
对一条边：
- 如果长度
<= x，走它不需要消耗免费额度； - 如果长度
> x，走它必须消耗一次免费额度。
于是固定 x 后，问题变成：从 1 到 n 的路径上，最少需要经过多少条长度大于 x 的边。
把边权改成 0/1：
text
长度 <= x：代价 0
长度 > x：代价 1用 0-1 BFS 求最小代价。如果最小代价 <= k，说明 x 可行；否则 x 太小。
因为 x 越大，超限边只会越少，所以可行性具有单调性，可以二分最小可行值。
代码
cpp
#include <bits/stdc++.h>
using namespace std;
const int MAXN = 1005;
const int MAXP = 10005;
const int INF = 1000000000;
int n, p, k;
int head[MAXN], to[MAXP * 2], weight_edge[MAXP * 2], nxt[MAXP * 2], edge_cnt;
int dist_count[MAXN];
void add_edge(int u, int v, int w) {
edge_cnt++;
to[edge_cnt] = v;
weight_edge[edge_cnt] = w;
nxt[edge_cnt] = head[u];
head[u] = edge_cnt;
}
void read_input() {
cin >> n >> p >> k;
for (int i = 1; i <= p; i++) {
int a, b, l;
cin >> a >> b >> l;
add_edge(a, b, l);
add_edge(b, a, l);
}
}
bool check(int limit) {
for (int i = 1; i <= n; i++) {
dist_count[i] = INF;
}
deque<int> que;
dist_count[1] = 0;
que.push_back(1);
while (!que.empty()) {
int u = que.front();
que.pop_front();
for (int i = head[u]; i != 0; i = nxt[i]) {
int v = to[i];
int cost = (weight_edge[i] > limit) ? 1 : 0;
if (dist_count[u] + cost < dist_count[v]) {
dist_count[v] = dist_count[u] + cost;
if (cost == 0) {
que.push_front(v);
} else {
que.push_back(v);
}
}
}
}
return dist_count[n] <= k;
}
void solve() {
if (!check(INF)) {
cout << -1 << '\n';
return;
}
int left = 0;
int right = 1000000;
int answer = -1;
while (left <= right) {
int mid = (left + right) / 2;
if (check(mid)) {
answer = mid;
right = mid - 1;
} else {
left = mid + 1;
}
}
cout << answer << '\n';
}
int main() {
ios::sync_with_stdio(false);
cin.tie(nullptr);
read_input();
solve();
return 0;
}复杂度
每次检查是
总时间复杂度为
总结
“最小化最大值”经常可以先尝试二分答案。
本题固定答案后，免费边数量变成了路径上的 0/1 代价，剩下就是一次最短路判断。