洛谷 P1948. Telephone Lines S

问题描述

在无向图上求出一条从 $1$ 到 $N$ 的路径，使路径上第 $K+1$ 大的边权尽可能小。

link

分析

题目要求从 $1$ 号点走到 $N$ 号点，选一条路径，其中最多 $K$ 条边可以免费，自己只需要付剩下边中权值最大的一条的费用。目标是让这个值尽量小；如果 $1$ 到 $N$ 根本不连通，则输出 $-1$。

关键转化：把"最多免费 $K$ 条边"看成走每条边时的两种决策——要么付费（当前最大花费变为它与这条边权值的较大者），要么使用一次免费名额（当前最大花费不变，但剩余免费次数减一）。于是问题变成在"节点 + 已用免费次数"组成的状态图上求最小花费。下面两种思路分别处理这个问题。

思路一：分层图 + DP（Dijkstra）

把"已用掉的免费次数"作为状态的第二维：设 $d[x][p]$ 表示从 $1$ 走到 $x$、用掉 $p$ 次免费名额时，所需支付的最大边权的最小值。

状态转移（对边 $x\to y$，权值为 $w$）：

• 付费：$d[y][p]=max(d[x][p],w)$，即新的最大花费取"历史最大值"与这条边权值中的较大者；
• 免费（当 $p<k$）：$d[y][p+1]=d[x][p]$，最大花费保持不变。

把二元组 $(x,p)$ 看作图上的一个点（即分层图中第 $p$ 层的点 $x$），从 $(1,0)$ 出发跑 Dijkstra。每次从堆中取出当前最小花费的状态，枚举其邻边，分别做付费与免费的更新。由于状态数只有 $N\times (K+1)$ 个，且每次更新得到的值只增不减，堆优化 Dijkstra 可以求出每个状态的准确最小值。

最终答案取 $\underset{0\le p\le k}{min}d[N][p]$；若该值仍为无穷大，说明 $1$ 与 $N$ 不连通，输出 $-1$。

复杂度：状态数 $O(NK)$，每个状态枚举所有出边，总转移数 $O(PK)$，堆优化后为 $O(K(N+P)\log (NK))$。

思路二：二分答案 + 01 最短路

注意到答案具有单调性：如果"支付上限为 $X$ 可行"（即存在一条从 $1$ 到 $N$ 的路径，路径上权值大于 $X$ 的边不超过 $K$ 条），那么对任意更大的上限也一定可行。因此可以二分支付上限 $\mathrm{mid}$，把问题转化为判定：

是否存在一条从 $1$ 到 $N$ 的路径，使得路径上权值大于 $\mathrm{mid}$ 的边不超过 $K$ 条？

判定时把边权"降维"：权值大于 $\mathrm{mid}$ 的边记为 $1$（代表一条"贵边"），其余记为 $0$。用最短路求出从 $1$ 到 $N$ 的最少贵边数量 $\mathrm{dist}[N]$，若 $\mathrm{dist}[N]\le k$，说明当前 $\mathrm{mid}$ 可行。由于边权只有 $0$ 和 $1$，除了 Dijkstra 之外也可以用 01 BFS（双端队列）做到线性判定。

关于二分边界：答案不可能超过最大边权，取 $r=1000001$ 作为哨兵。若二分结束后答案仍是哨兵值，说明不可达，输出 $-1$；否则输出 $r$。

复杂度：二分 $O(\log C)$ 次（$C$ 为边权上限），每次判定跑一遍最短路 $O(P\log N)$，总体 $O(\log C\cdot P\log N)$。

参考代码

思路一：分层图 + DP 实现

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

typedef pair<int, pair<int, int>> PIII;

const int N = 1010, M = 20010;
int h[N], e[M], w[M], ne[M], idx = 1;
int vis[N][10010];
int d[N][10010];
int n, m, k;

void add(int a, int b, int c) {
    e[idx] = b;
    w[idx] = c;
    ne[idx] = h[a];
    h[a] = idx++;
}

int dijkstra() {
    memset(d, 0x3f, sizeof d);
    d[1][0] = 0;

    priority_queue<PIII, vector<PIII>, greater<PIII>> heap;
    heap.push({d[1][0], {1, 0}});

    while (heap.size()) {
        auto t = heap.top();
        heap.pop();

        int x = t.second.first, p = t.second.second, dis = t.first;

        if (vis[x][p]) continue;
        vis[x][p] = 1;

        for (int i = h[x]; i; i = ne[i]) {
            int y = e[i];
            if (d[y][p] > max(dis, w[i])) {
                d[y][p] = max(dis, w[i]);
                heap.push({d[y][p], {y, p}});
            }
            if (p < k && d[y][p + 1] > dis) {
                d[y][p + 1] = dis;
                heap.push({d[y][p + 1], {y, p + 1}});
            }
        }
    }

    int ans = 0x3f3f3f3f;
    for (int p = 0; p <= k; p++) ans = min(ans, d[n][p]);
    return ans == 0x3f3f3f3f ? -1 : ans;
}

int main() {
    cin >> n >> m >> k;

    for (int i = 1; i <= m; i++) {
        int a, b, c; cin >> a >> b >> c;
        add(a, b, c);
        add(b, a, c);
    }

    cout << dijkstra() << endl;

    return 0;
}

思路二：二分

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

const int N = 1010, M = 20010;
int head[N], e[M], w[M], ne[M], idx;
int dist[N], vis[N];
int n, p, k;

void add(int a, int b, int c) {
    e[idx] = b;
    w[idx] = c;
    ne[idx] = head[a];
    head[a] = idx++;
}

bool check(int mid) {
    memset(dist, 0x3f, sizeof dist);
    memset(vis, false, sizeof vis);

    priority_queue<pair<int, int>, vector<pair<int, int>>, greater<pair<int, int>>> q;
    dist[1] = 0;
    q.push({dist[1], 1});

    while (q.size()) {
        auto t = q.top(); q.pop();
        int x = t.second;

        if (vis[x]) continue;
        vis[x] = true;

        for (int i = head[x]; i != -1; i = ne[i]) {
            int y = e[i], v = w[i] > mid ? 1 : 0;
            if (dist[y] > dist[x] + v) {
                dist[y] = dist[x] + v;
                q.push({dist[y], y});
            }
        }
    }

    return dist[n] <= k;
}

int main() {
    memset(head, -1, sizeof head);
    cin >> n >> p >> k;
    for (int i = 0; i < p; i++) {
        int a, b, c; cin >> a >> b >> c;
        add(a, b, c);
        add(b, a, c);
    }

    int l = 0, r = 1000001;
    while (l < r) {
        int mid = l + r >> 1;
        if (check(mid)) r = mid;
        else l = mid + 1;
    }
    if (r != 1000001) cout << r << endl;
    else cout << -1 << endl;

    return 0;
}