T29803: 穿越火线

Dijkstra, binary search, http://cs101.openjudge.cn/practice/29803/

你是战场上的一名司机,现在需要在时限T内把物资从大本营送到前线。从战场的地图可以视为一张无向图(可能有重边),其中每条边代表一条道路,每条道路除了通过时间t以外,还有一个交火等级a,这里a是0~100之间的整数。一般来说,车辆的防护等级要大于等于交火等级才能通过这条道路。不过,你有一个一次性的光学迷彩,可以让你无视交火等级地通过某一条道路。请计算为了按时把物资运到指定地点,车辆的防护等级至少要是多少.

输入

第一行三个整数n,m,T，表示战场的节点数，边数和要求的时限。大本营是1号，前线是n号节点。接下来m行，每行四个整数u,v,t,a，表示节点u和节点v之间有一条道路，通过时间为t，交火等级为m。

输出

一个正整数，表示车辆需要的最小防护等级。数据保证100的防护等级下可以按时到达。

样例输入

样例输出

提示

从1到4有1-2-4和1-3-4两条路径，但是路线1-2-4需要总时间8，超过时间要求。所以只能走1-3-4.两条道路需要的防护等级分别为50和60，可以在后一条道路上使用光学迷彩，所以防护等级只需要是50.

这是一个结合了 最短路径 + 二分答案 + 特殊处理一次性道具 的问题，具体思路如下：

✅ 问题理解

我们要：

从节点 1 到 n；
时间总花费 ≤ T；
道路有交火等级 a，只有当 防护等级 ≥ a 才能通过；
我们可以 一次性无视 一条边的交火等级。

目标是求：能按时到达的最小防护等级。

🧠 解题思路

步骤一：二分答案

我们设防护等级为 x，我们要找满足以下条件的最小 x：

存在一条从 1 到 n 的路径，总时间 ≤ T；
在这条路径上：
- 所有边要么 a ≤ x；
- 最多一条边 a > x（我们用光学迷彩）。

所以我们可以 二分防护等级 x ∈ [0, 100]，判断在当前 x 下是否可行。

步骤二：判定函数 check(x)

对于某个防护等级 x，我们要判断：能否在总时间 ≤ T 的情况下，从 1 到 n？

方法：

枚举所有边，把它们分类：
- 普通边：a ≤ x，可直接走；
- 特权边：a > x，可以最多选择其中一条使用光学迷彩。
对于每个 特权边，试图在图中加上这条特权边，其它只能走普通边，跑一次 Dijkstra，看从 1 到 n 是否可达且时间 ≤ T。

✅ 实现代码（Python）

python

import heapq

def dijkstra(n, graph, allowed_edges):
    dist = [float('inf')] * (n + 1)
    dist[1] = 0
    pq = [(0, 1)]
    while pq:
        time, u = heapq.heappop(pq)
        if time > dist[u]:
            continue
        for v, t in allowed_edges[u]:
            if dist[v] > time + t:
                dist[v] = time + t
                heapq.heappush(pq, (dist[v], v))
    return dist[n]

def check(x, n, T, edges):
    graph = [[] for _ in range(n + 1)]
    special_edges = []

    for u, v, t, a in edges:
        if a <= x:
            graph[u].append((v, t))
            graph[v].append((u, t))
        else:
            special_edges.append((u, v, t))

    # 尝试不使用光学迷彩
    if dijkstra(n, edges, graph) <= T:
        return True

    # 尝试每一条特权边作为迷彩边
    for u, v, t in special_edges:
        # 暂时加上这条边
        graph[u].append((v, t))
        graph[v].append((u, t))
        if dijkstra(n, edges, graph) <= T:
            return True
        # 撤销
        graph[u].pop()
        graph[v].pop()

    return False

def min_armor(n, m, T, edge_list):
    left, right = 0, 100
    answer = 100
    while left <= right:
        mid = (left + right) // 2
        if check(mid, n, T, edge_list):
            answer = mid
            right = mid - 1
        else:
            left = mid + 1
    return answer

# 读入样例输入
n, m, T = map(int, input().split())
edges = [tuple(map(int, input().split())) for _ in range(m)]

print(min_armor(n, m, T, edges))

T29803: 穿越火线 ​

T29803: 穿越火线