通往奥格瑞玛的道路

题目背景

在艾泽拉斯大陆上有一位名叫歪嘴哦的神奇术士，他是部落的中坚力量。

有一天他醒来后发现自己居然到了联盟的主城暴风城。

在被众多联盟的士兵攻击后，他决定逃回自己的家乡奥格瑞玛。

题目描述

在艾泽拉斯，有 $n$ 个城市。编号为 $1,2,3,\ldots,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\leq a_i,b_i\leq n$）。表示城市 $a_i$ 和城市 $b_i$ 之间有一条公路，如果从城市 $a_i$ 到城市 $b_i$，或者从城市 $b_i$ 到城市 $a_i$，会损失 $c_i$ 的血量。

输出格式

仅一个整数，表示歪嘴哦交费最多的一次的最小值。

如果他无法到达奥格瑞玛，输出 AFK。

样例 #1

样例输入 #1

样例输出 #1

提示

对于 $60\%$ 的数据，满足 $n\leq 200$，$m\leq 10^4$，$b\leq 200$；

对于 $100\%$ 的数据，满足 $1\leq n\leq 10^4$，$1\leq m\leq 5\times 10^4$，$1\leq b\leq 10^9$；

对于 $100\%$ 的数据，满足 $1\leq c_i\leq 10^9$，$0\leq f_i\leq 10^9$，可能有两条边连接着相同的城市。

题目分析

题目目的：求出最小的每条道路经过的城市收费的最大值。

首先可发现一个非常明显的最小化最大值问题，可以联想到使用二分答案来解决。当然，二分答案的前提是查找的对象具有有序性。先理解下“对于每条道路经过的城市收费的最大值”是什么意思，意思指的就是有一条从起点到终点的路径，每个点、每条边都有个权值，所有经过的点的点权中的最大值。图中可能存在多条从起点出发到达终点的路径，我们要求出最小的经过点权的最大值。

我们所有路径的选择，都需要满足一个基础的条件那就是能够让我们从起点处到达终点处。而对于经过边权的最大值又会影响些什么呢？明显的一点就是，最大值越大，我可挑选的边也就越多，我就更有可能从起点走到终点。我们设 $chk(x)$ 为经过边的最大点权为 $x$ ，能否从起点到达终点。若 $chk(x_i)$ 不满足要求，那么 $<x_i$ 自然也都不满足要求；若 $chk(x_j)$ 满足要求，那么 $>x_j$ 的自然也都满足要求了，此时可发现具备广义的有序性，那么就可以使用二分答案的思路进行处理。

最小化最大值框架

int L=MINS,R=MAXS;
int ans=-1;
while(L<=R){
    int mid=(L+R)/2;
    if(chk(mid)){
        ans=mid;
        R=mid-1;
    }else{
        L=mid+1;
    }
}
cout<<ans;

接下来考虑可行性问题 $chk(x)$ 如何实现。

在过程中边权最大值上限限制了可选择的边，且题目中还存在血量限制。那么我们可以用最短路的思路求出在边权首先情况下的从起点到终点的最短路径的边权总和，根据总和与血量 $b$ 之前的大小关系去判断能否到达终点。

而对于最短路部分可以采用单源最短路算法 Dijkstra 进行实现。

代码实现

#include <bits/stdc++.h>
using namespace std;
using i64 = long long;
const int N = 1e4 + 5;
int n, m, B;
struct node {
  int v;
  i64 w;
  friend bool operator<(const node &A, const node &B) { return A.w > B.w; }
};
vector<node> G[N];
int f[N];
i64 dis[N];
bool vis[N];
bool chk(int mid) {
  // 经过路径点权最大限制为mid时，是否能够到达终点
  // 基于Dijkstra最短路算法
  priority_queue<node> q;
  memset(dis, 0x3f, sizeof(dis));
  memset(vis, 0, sizeof(vis));
  if (f[1] <= mid) {  // 过路费收费包括起点和终点
    dis[1] = 0;
    q.push({1, 0});
  }
  while (!q.empty()) {
    node cur = q.top();
    q.pop();

    int u = cur.v;
    vis[u] = 1;
    for (auto e : G[u]) {
      int v = e.v;
      i64 w = e.w;
      if (vis[v]) continue;
      if (f[v] > mid) continue;  // 跳过过路费超过限制的
      if (dis[v] > dis[u] + w) {
        dis[v] = dis[u] + w;
        q.push({v, dis[v]});
      }
    }
  }
  // 消耗血量<=B
  return dis[n] <= B;
}
int main() {
  ios::sync_with_stdio(false);
  cin.tie(nullptr);
  cout.tie(nullptr);

  int a = 0, b = 0, c = 0;
  int L = 0, R = 0;
  cin >> n >> m >> B;
  for (int i = 1; i <= n; i++) {
    cin >> f[i];
    L = min(L, f[i]);
    R = max(R, f[i]);
  }
  // 邻接表存图
  for (int i = 1; i <= m; i++) {
    cin >> a >> b >> c;
    G[a].push_back(node{b, c});
    G[b].push_back(node{a, c});
  }
  // 二分答案：最小化最大值框架
  int ans = -1;
  while (L <= R) {
    int mid = (L + R) / 2;
    if (chk(mid)) {
      ans = mid;
      R = mid - 1;
    } else {
      L = mid + 1;
    }
  }
  if (ans == -1)
    cout << "AFK";
  else
    cout << ans;
  return 0;
}

【题解】通往奥格瑞玛的道路