题目地址：

https://www.luogu.com.cn/problem/P1462

题目背景：
在艾泽拉斯大陆上有一位名叫歪嘴哦的神奇术士，他是部落的中坚力量。有一天他醒来后发现自己居然到了联盟的主城暴风城。在被众多联盟的士兵攻击后，他决定逃回自己的家乡奥格瑞玛。

题目描述：
在艾泽拉斯，有$n$个城市。编号为$1,2,3,\dots ,n$。城市之间有$m$条双向的公路，连接着两个城市，从某个城市到另一个城市，会遭到联盟的攻击，进而损失一定的血量。每次经过一个城市，都会被收取一定的过路费（包括起点和终点）。路上并没有收费站。假设$1$为暴风城，$n$为奥格瑞玛，而他的血量最多为$b$，出发时他的血量是满的。如果他的血量降低至负数，则他就无法到达奥格瑞玛。歪嘴哦不希望花很多钱，他想知道，在可以到达奥格瑞玛的情况下，他所经过的所有城市中最多的一次收取的费用的最小值是多少。

输入格式：
第一行$3$个正整数，$n,m,b$。分别表示有$n$个城市，$m$条公路，歪嘴哦的血量为$b$。
接下来有$n$行，每行$1$个正整数，$f_i$。表示经过城市$i$，需要交费$f_i$元。
再接下来有$m$行，每行$3$个正整数，$a_i,b_i,c_i$（$1\le a_i,b_i\le n$）。表示城市$a_i$和城市$b_i$之间有一条公路，如果从城市$a_i$到城市$b_i$，或者从城市$b_i$到城市$a_i$，会损失$c_i$的血量。

输出格式：
仅一个整数，表示歪嘴哦交费最多的一次的最小值。如果他无法到达奥格瑞玛，输出AFK。

数据范围：
对于$60\%$的数据，满足$n\le 200$，$m\le 10^4$，$b\le 200$；
对于$100\%$的数据，满足$n\le 10^4$，$m\le 5\times 10^4$，$b\le 10^9$；
对于$100\%$的数据，满足$c_i\le 10^9$，$f_i\le 10^9$，可能有两条边连接着相同的城市。

思路是二分答案 + 最短路。本题是要求在保证血量不变为负的前提下，单次最大收费的最小值可以是多少。容易知道，对于单次最大收费小于等于$x$的情形如果存在方案，那么对于更大的$x$当然也存在方案。从而我们可以用二分。由于起点和终点显然是要收费的，所以二分左端点为 max ⁡ { f 1 , f n } \max\{f_1,f_n\} max{f1​,fn​}；单次最大收费的最大可能即为${\max }_i{f}_i$，此为右端点。对于每个位于区间内的$x$，我们判断只走收费不超过$x$的城市，是否能从$1$走到$n$，也即判断从$1$走到$n$，如果将耗血量视为费用，最短路长度是否小于等于$b$，可以用Dijkstra算法来做。如果能，则收缩右端点；否则收缩左端点。代码如下：

#include 
#include 
#include 
using namespace std;
using PLI = pair<long, int>;

const int N = 10010, M = 100010;
int n, m, b, fee[N];
int h[N], e[M], ne[M], w[M], idx;
long dist[N];
bool vis[N];

#define add(a, b, c) \
e[idx] = b, ne[idx] = h[a], w[idx] = c, h[a] = idx++

int dijkstra(int maxf) {
  memset(dist, 0x3f, sizeof dist);
  memset(vis, 0, sizeof vis);
  dist[1] = 0;
  priority_queue<PLI, vector<PLI>, greater<PLI>> heap;
  heap.push({0, 1});
  while (heap.size()) {
    auto t = heap.top(); heap.pop();
    int u = t.second;
    if (vis[u]) continue;
    if (u == n) break;
    vis[u] = true;
    for (int i = h[u]; ~i; i = ne[i]) {
      int v = e[i];
      if (fee[v] > maxf) continue;
      if (dist[u] + w[i] < dist[v]) {
        dist[v] = dist[u] + w[i];
        heap.push({dist[v], v});
      }
    }
  }

  return dist[n];
}

int main() {
  memset(h, -1, sizeof h);
  scanf("%d%d%d", &n, &m, &b);
  int l = 0, r = 0;
  for (int i = 1; i <= n; i++) {
    scanf("%d", &fee[i]);
    r = max(r, fee[i]);
  }
  l = max(fee[1], fee[n]);
  for (int i = 1; i <= m; i++) {
    int a, b, c;
    scanf("%d%d%d", &a, &b, &c);
    add(a, b, c), add(b, a, c);
  }

  while (l < r) {
    int mid = l + (r - l >> 1);
    if (dijkstra(mid) <= b) r = mid;
    else l = mid + 1;
  }

  if (dijkstra(l) > b) puts("AFK");
  else printf("%d\n", l);
}
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

时间复杂度$O(m\log n\log (R-L))$， L = max ⁡ { f 1 , f n } , R = max ⁡ i f i L=\max\{f_1,f_n\}, R=\max_i f_i L=max{f1​,fn​},R=maxi​fi​，空间$O(n+m)$。