架设电话线

形式化题目

给定一个无向带权图 $G = (V, E)$ ，包含 $N$ 个顶点和 $P$ 条无向边，每条边 $e$ 拥有非负权值 $w(e)$ 。给定整数 $K \geqslant 0$ 。

求一条从顶点 $1$ 到顶点 $N$ 的路径 $Path = (e_1, e_2, \dots, e_m)$ ，允许从该路径中至多选出 $K$ 条边免费（权值视作 $0$ ），使得剩余边中的最大权值最小。即：

\min_{Path} \left( \min_{S \subseteq Path, |S| \leqslant K} \max_{e \in Path \setminus S} w(e) \right)

（若

|Path| \leqslant K

，则费用为

0

；若不存在从

1

到

N

的路径，输出

-1

）。

样例解释

对于输入样例：

节点数 $N = 5$ ，边数 $P = 7$ ，免费边数 $K = 1$ 。
选择路径 $1 \to 3 \to 4 \to 5$ ：
- 边 $(1, 3)$ 权值为 $4$ ；
- 边 $(3, 4)$ 权值为 $7$ ；
- 边 $(4, 5)$ 权值为 $6$ 。
允许免费升级 $1$ 条边，指定最贵的边 $(3, 4)$ （花费 $7$ ）免费；
剩余边为 $(1, 3)$ （花费 $4$ ）与 $(4, 5)$ （花费 $6$ ），最大花费为 $6$ 。
若改选路径 $1 \to 2 \to 3 \to 4 \to 5$ ：
- 边包含 $(1, 2)$ 权值 $5$ 、 $(2, 3)$ 权值 $3$ 、 $(3, 4)$ 权值 $7$ 、 $(4, 5)$ 权值 $6$ 。
- 免费一条边仍无法将最大花费压到 $4$ 。
重新审视更优路径：选择路径 $1 \to 3 \to 2 \to 4 \to 5$ ：
- 边 $(1, 3)$ 权值为 $4$ ；
- 边 $(3, 2)$ 权值为 $3$ ；
- 边 $(2, 4)$ 权值为 $8$ （免费该边）；
- 边 $(4, 5)$ 权值为 $6$ 。此时剩余边最大值为 $6$ 。
实际上选择路径 $1 \to 3 \to 4 \to 5$ 时也可以免费边 $(4, 5)$ 吗？不是。
观察更优路径： $1 \to 2 \to 5$ （边权 $5, 9$ ），免费 $9$ ，花费 $5$ 。
观察路径 $1 \to 3 \to 2 \dots$ ：若选择路径 $1 \to 3 \to 4 \dots$ ；是否存在一条路径使得除 1 条边外其余边均 $\leqslant 4$ ？检查 $1 \to 3$ （权值 4），接下来从 $3$ 无法只用 $\leqslant 4$ 的边走到 $5$ 且只有一条 $> 4$ 的边：路径 $1 \xrightarrow{4} 3 \xrightarrow{3} 2$ （两条边权均 $\leqslant 4$ ），再从 $2$ 到 $5$ （权值 $9$ ），在此路径上权值分别为 $4, 3, 9$ 。将最长的边 $(2, 5)$ （权值 $9$ ）免费掉，剩余边权最大值为 $\max(4, 3) = 4$ 。因此最小花费为 $4$ 。

graph LR
    1((1)) ---|4| 3((3))
    3 ---|3| 2((2))
    2 ---|9 [免费]| 5((5))
    classDef free stroke:#f00,stroke-width:2px,stroke-dasharray: 5 5;

正解

思路

要求最小化路径上“除去最大的 $K$ 条边后，剩余边权的最大值”。这种“最大值最小”或“第 $K+1$ 大值最小”的形式具有典型的二分单调性：

单调性分析：假设所求的花费上限为 $X$ 。如果存在一条从 $1$ 到 $N$ 的路径，在其上权值大于 $X$ 的边数不超过 $K$ 条，那么我们只要将这些大于 $X$ 的边指定为免费，其余边的花费均不超过 $X$ ，总花费便不超过 $X$ 。显然，当 $X$ 增大时，满足条件的路径只会更多不会更少。因此判定结果关于 $X$ 具有单调性，可以二分答案 $X$ 。
判定问题转化（0-1 赋权与最短路）：对于固定的阈值 $X$ ：
- 若某条边的边权 $w(e) \leqslant X$ ，说明无需占用免费名额，权重记为 $0$ ；
- 若某条边的边权 $w(e) > X$ ，说明必须消耗一次免费名额，权重记为 $1$ 。
此时，问题转化为：在边权只有 $0$ 和 $1$ 的新图上，求从起点 $1$ 到终点 $N$ 的最短路径长度 $dist[N]$ 。
- 若 $dist[N] \leqslant K$ ，说明可以通过不超过 $K$ 次免费操作使得最大边权不超过 $X$ ，该 $X$ 可行；
- 若 $dist[N] > K$ ，说明至少需要消耗超过 $K$ 次免费机会，该 $X$ 不可行。
0-1 BFS 高效求解：由于新图中边权只有 $0$ 和 $1$ ，无需使用带 $\log$ 复杂度的 Dijkstra 堆优化，直接使用双端队列（deque）进行 0-1 BFS：
- 转移边权为 $0$ 时，将新节点压入队头（appendleft）；
- 转移边权为 $1$ 时，将新节点压入队尾（append）。单次判定时间复杂度仅为 $O(N + P)$ 。
无解处理：若原图上起点 $1$ 与终点 $N$ 根本不连通，无论多少免费名额都无法到达，判定直接输出 $-1$ 。

代码

Python 版：

python

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75#!/usr/bin/env python3
# Author by Rainboy blog: https://rainboylv.com github: https://github.com/rainboylvx
# rbook: -> https://rbook.roj.ac.cn  https://rbook2.roj.ac.cn
# rainboy的学习导航网站: https://idx.roj.ac.cn
# create_at: 2026-09-30 14:45
# update_at: 2026-09-30 14:45

import sys
from collections import deque

INF = 10**9


def min_cost_edges(graph: list[list[tuple[int, int]]], threshold: int, n: int) -> int:
    """计算从 1 到 n 路径上边权大于 threshold 的最少边数（0-1 BFS）。"""
    dist = [INF] * (n + 1)
    dist[1] = 0
    dq = deque([1])

    while dq:
        u = dq.popleft()
        if u == n:
            break
        d = dist[u]
        for v, w in graph[u]:
            cost = 1 if w > threshold else 0
            if d + cost < dist[v]:
                dist[v] = d + cost
                if cost == 0:
                    dq.appendleft(v)
                else:
                    dq.append(v)

    return dist[n]


def solve() -> None:
    tokens = sys.stdin.buffer.read().split()
    if not tokens:
        return
    data = iter(map(int, tokens))

    n = next(data)
    p = next(data)
    k = next(data)

    graph: list[list[tuple[int, int]]] = [[] for _ in range(n + 1)]
    max_len = 0
    for _ in range(p):
        u, v, w = next(data), next(data), next(data)
        graph[u].append((v, w))
        graph[v].append((u, w))
        if w > max_len:
            max_len = w

    # 若 1 与 n 之间连通性不足，直接判 -1
    if min_cost_edges(graph, INF, n) == INF:
        print(-1)
        return

    # 二分寻找最小的阈值 mid，使得大于 mid 的边数 <= k
    low, high, ans = 0, max_len, max_len
    while low <= high:
        mid = (low + high) // 2
        if min_cost_edges(graph, mid, n) <= k:
            ans = mid
            high = mid - 1
        else:
            low = mid + 1

    print(ans)


if __name__ == "__main__":
    solve()

C++ 版（同一算法）：

cpp

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
86
87
88
89
90
91
92
93
94
95
96
97
98
99
100
101
102
103
104
105/**
 * Author by Rainboy blog: https://rainboylv.com github: https://github.com/rainboylvx
 * rbook: -> https://rbook.roj.ac.cn  https://rbook2.roj.ac.cn
 * rainboy的学习导航网站: https://idx.roj.ac.cn
 * create_at: 2026-10-05 04:26
 * update_at: 2026-10-05 04:26
 */
#include <bits/stdc++.h>
using namespace std;

typedef long long ll;

const int MAXN = 1005;   // 基站数上限（N <= 1000）
const int MAXM = 20005;  // 无向边，正向反向各存一条（P <= 10000）
const ll INF = 1e18;

// 题目数据
int n, p, k;
// 链式前向星存无向图
int head[MAXN], nxt[MAXM], to[MAXM], edge_cnt;
ll w[MAXM];        // w[i] 为第 i 条边的升级花费
ll dist[MAXN];     // dist[u]：1 到 u 路径上边权大于阈值的边的最少条数（0-1 BFS 距离）

// 加一条 u <-> v、花费 c 的无向边。
void add_edge(int u, int v, ll c) {
    edge_cnt++;
    to[edge_cnt] = v;
    w[edge_cnt] = c;
    nxt[edge_cnt] = head[u];
    head[u] = edge_cnt;
}

// 0-1 BFS：判定阈值 limit，返回 1 到 n 路径上权值大于 limit 的边的最少条数；
// 不可达返回 INF。
ll bfs01(ll limit) {
    for (int i = 1; i <= n; i++) dist[i] = INF;
    dist[1] = 0;
    deque<int> dq;  // 0-1 BFS 的双端队列：0 边进队头，1 边进队尾
    dq.push_back(1);
    while (!dq.empty()) {
        int u = dq.front();
        dq.pop_front();
        for (int i = head[u]; i; i = nxt[i]) {
            int v = to[i];
            // 边权不超过阈值的花 0 个免费名额，超过阈值的花 1 个
            ll cost = (w[i] > limit) ? 1 : 0;
            if (dist[u] + cost < dist[v]) {
                dist[v] = dist[u] + cost;
                if (cost == 0) dq.push_front(v);
                else dq.push_back(v);
            }
        }
    }
    return dist[n];
}

void read_input() {
    cin >> n >> p >> k;
    edge_cnt = 0;
    for (int i = 1; i <= p; i++) {
        int a, b;
        ll l;
        cin >> a >> b >> l;
        add_edge(a, b, l);
        add_edge(b, a, l);
    }
}

void solve() {
    // 先判连通性：阈值取极大值时所有边花费都是 0，等价于普通 BFS
    if (bfs01(INF) == INF) {
        cout << -1 << endl;
        return;
    }

    // 找到最大的边权作为二分上界
    ll max_len = 0;
    for (int i = 1; i <= edge_cnt; i++) {
        if (w[i] > max_len) max_len = w[i];
    }

    // 二分答案：最小的阈值 mid，使得路径上大于 mid 的边数不超过 k
    ll low = 0, high = max_len, ans = max_len;
    while (low <= high) {
        ll mid = (low + high) / 2;
        if (bfs01(mid) <= k) {
            ans = mid;      // mid 可行，尝试更小的花费
            high = mid - 1;
        } else {
            low = mid + 1;
        }
    }

    cout << ans << endl;
}

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

    read_input();
    solve();

    return 0;
}

复杂度

时间复杂度：
- 二分区间为 $[0, \max(L)]$ ，二分判定次数为 $O(\log(\max L))$ ，在 $\max L \leqslant 10^6$ 时约 20 次。
- 每次判定运行一次 0-1 BFS，时间复杂度为 $O(N + P)$ 。
- 总体时间复杂度为 $O((N + P) \log(\max L))$ 。当 $N \leqslant 1000, P \leqslant 10000$ 时，总操作次数在 $2 \times 10^5$ 左右，可在几十毫秒内完成。
空间复杂度： $O(N + P)$ ，用于存储图的邻接表、距离数组以及双端队列。

总结

本题是「二分答案 + 0-1 BFS」的经典模型：

将复杂的最优费用函数（第 $K+1$ 大边权）转化为可行性判定；
将“阈值以上/以下”映射为图上的“0/1 权值”，将判定问题转化为边权为 0/1 的单源最短路；
利用双端队列 0-1 BFS 将每次判定的复杂度优化到线性 $O(N + P)$ 。

目录

形式化题目

样例解释

正解

思路

代码

复杂度

总结