T21515: 电话线路

dijkstra, binary search, http://cs101.openjudge.cn/practice/21515/

有N座通信基站，P条双向电缆，第i条电缆连接基站Ai和Bi。特别地，1号基站是通信公司的总站，N号基站位于一座农场中。现在，农场主希望对通信线路进行升级，其中升级第i条电缆需要花费Li。

电话公司正在举行优惠活动。农场主可以指定一条从1号基站到N号基站的路径，然后，农场主可以指定路径上不超过K条电缆，先由电话公司免费提供升级服务。农场主只需要支付在该路径上剩余的电缆中，升级价格最贵的那条电缆的花费即可。支付完成后，其余电缆也将由电话公司免费升级。求至少用多少钱能完成升级。

输入

第一行三个整数， N，P，K。接下来P行，每行三个整数Ai，Bi，Li。

输出

若不存在从1到N的路径，输出-1。否则输出所需最小费用。

样例输入

样例输出

提示

0 ≤ K < N ≤ 1000 1 ≤ P ≤ 2000

python

import sys
from collections import deque


def main():
    data = sys.stdin.read().split()
    if not data:
        return

    it = iter(data)
    n = int(next(it));
    p = int(next(it));
    k = int(next(it))

    graph = [[] for _ in range(n + 1)]
    max_edge = 0
    for _ in range(p):
        a = int(next(it));
        b = int(next(it));
        l = int(next(it))
        graph[a].append((b, l))
        graph[b].append((a, l))
        if l > max_edge:
            max_edge = l

    # 特殊情况：如果 1 和 n 不连通？0-1 BFS 会处理（dist[n] 保持 inf）

    def can(x):
        # dist[i] = 从 1 到 i 路径上 权重 > x 的边的最小数量
        INF = 10 ** 9
        dist = [INF] * (n + 1)
        dist[1] = 0
        dq = deque([1])

        while dq:
            u = dq.popleft()
            for v, w in graph[u]:
                # 如果 w <= x，这条边免费（不计入代价）；否则代价为1
                cost = 1 if w > x else 0
                new_cost = dist[u] + cost
                if new_cost < dist[v] and new_cost <= k:  # 剪枝：超过k没必要继续
                    dist[v] = new_cost
                    if cost == 0:
                        dq.appendleft(v)
                    else:
                        dq.append(v)
        return dist[n] <= k

    # 二分答案：最小的 x 使得 can(x) 为 True
    lo = 0
    hi = max_edge + 1  # 注意：答案可能为0，也可能需要比max_edge更大？但题目允许K>=0，所以max_edge足够

    # 但注意：有可能最优解是0（所有边<=0？但Li>=0），或甚至不需要任何边>lim
    # 另外，有可能即使 lim = max_edge 也不连通 → 输出 -1

    if not can(hi):
        print(-1)
        return

    ans = -1
    while lo < hi:
        mid = (lo + hi) // 2
        if can(mid):
            ans = mid
            hi = mid
        else:
            lo = mid + 1

    print(ans)


if __name__ == "__main__":
    main()

python

#2200015507 王一粟
from heapq import *
n,p,k = map(int,input().split())
graph = {i:{} for i in range(1,n+1)}
h = 0
for _ in range(p):
    a,b,l = map(int,input().split())
    graph[a][b] = graph[b][a] = l
    h = max(h,l)
l = 0

def search(lim):
    heap = [(-1,-k)]
    heapify(heap)
    vis = {}
    while heap:
        idx,free = heappop(heap)
        idx,free = -idx,-free
        if idx == n:
            return 1
        if idx not in vis or vis[idx] < free:
            vis[idx] = free
        else:
            continue
        for t,length in graph[idx].items():
            new_free = free
            if length > lim:
                if new_free > 0:
                    new_free -= 1
                else:
                    continue
            if t in vis and vis[t] > new_free:
                continue
            heappush(heap,(-t,-new_free))
    return 0
while l < h:
    if l +1 == h:
        ans_l,ans_h = search(l),search(h)
        if ans_l == ans_h == 0:
            print(-1)
        else:
            print(l if ans_l else h)
        exit()
    mid = (l+h)//2
    if search(mid):
        h = mid
    else:
        l = mid

T21515: 电话线路 ​

T21515: 电话线路