二分允许的最高城市收费，用受限 Dijkstra 检查血量能否到达终点。
OJ: luogu
题目 ID: P1462
难度:普及+/提高-
标签:二分答案Dijkstra最短路python
日期: 2026-07-17 03:00
题意
总伤害不能超过血量，最小化所经城市收费的最大值。
思路
固定收费上限后，只允许进入收费不超过上限的城市，运行 Dijkstra 求最小伤害；能否到达具有单调性，因此在去重后的收费列表上二分。最高收费仍不可达则输出 AFK。
Python 知识
sorted(set(fee))同时得到离散二分候选。- Dijkstra 中把
health+1作为无穷大，并剪掉超过血量的状态。 - 提前弹出终点即可结束判定。
代码
python
import sys
from heapq import heappop, heappush
input = sys.stdin.buffer.readline
n, edges, health = map(int, input().split())
fee = [0] + [int(input()) for _ in range(n)]
graph = [[] for _ in range(n + 1)]
for _ in range(edges):
u, v, damage = map(int, input().split())
graph[u].append((v, damage))
graph[v].append((u, damage))
def feasible(limit):
if fee[1] > limit or fee[n] > limit:
return False
infinity = health + 1
distance = [infinity] * (n + 1)
distance[1] = 0
heap = [(0, 1)]
while heap:
current, node = heappop(heap)
if current != distance[node]:
continue
if node == n:
return True
for neighbor, damage in graph[node]:
candidate = current + damage
if fee[neighbor] <= limit and candidate < distance[neighbor] and candidate <= health:
distance[neighbor] = candidate
heappush(heap, (candidate, neighbor))
return False
fees = sorted(set(fee[1:]))
if not feasible(fees[-1]):
print("AFK")
else:
left, right = 0, len(fees) - 1
while left < right:
middle = (left + right) // 2
if feasible(fees[middle]):
right = middle
else:
left = middle + 1
print(fees[left])原有 C++ 版本仍保留：
cpp
#include <bits/stdc++.h>
using namespace std;
const int MAXN = 10005;
const int MAXM = 100005;
const long long INF = (1LL << 62);
struct Edge {
int to;
int next;
int w;
};
int n, m;
long long blood_limit;
int fee[MAXN];
int head[MAXN], edge_cnt;
Edge edges[MAXM];
long long dist_node[MAXN];
void add_edge(int u, int v, int w) {
edge_cnt++;
edges[edge_cnt].to = v;
edges[edge_cnt].w = w;
edges[edge_cnt].next = head[u];
head[u] = edge_cnt;
}
bool check(int limit) {
if (fee[1] > limit || fee[n] > limit) {
return false;
}
for (int i = 1; i <= n; i++) {
dist_node[i] = INF;
}
priority_queue<pair<long long, int>, vector<pair<long long, int> >, greater<pair<long long, int> > > pq;
dist_node[1] = 0;
pq.push(make_pair(0, 1));
while (!pq.empty()) {
long long d = pq.top().first;
int u = pq.top().second;
pq.pop();
if (d != dist_node[u]) {
continue;
}
if (u == n) {
return d <= blood_limit;
}
for (int e = head[u]; e != 0; e = edges[e].next) {
int v = edges[e].to;
if (fee[v] > limit) {
continue;
}
long long nd = d + edges[e].w;
if (nd < dist_node[v]) {
dist_node[v] = nd;
pq.push(make_pair(nd, v));
}
}
}
return dist_node[n] <= blood_limit;
}
int main() {
ios::sync_with_stdio(false);
cin.tie(nullptr);
cin >> n >> m >> blood_limit;
int max_fee = 0;
for (int i = 1; i <= n; i++) {
cin >> fee[i];
max_fee = max(max_fee, fee[i]);
}
for (int i = 1; i <= m; i++) {
int u, v, w;
cin >> u >> v >> w;
add_edge(u, v, w);
add_edge(v, u, w);
}
if (!check(max_fee)) {
cout << "AFK\n";
return 0;
}
int left = max(fee[1], fee[n]);
int right = max_fee;
while (left < right) {
int mid = (left + right) >> 1;
if (check(mid)) {
right = mid;
} else {
left = mid + 1;
}
}
cout << left << '\n';
return 0;
}复杂度
时间 O((n+m)log n log n)，空间 O(n+m)。
总结
目标是最小化路径上的最大属性时，常用属性阈值二分加可达性检查。