洛谷 P1462 通往奥格瑞玛的道路

// P1462 通往奥格瑞玛的道路 —— ★ 这一版就能 AC
//
// 题目要的是：在所有「血量够用」的路线里，**路径上单次过路费最大值**的**最小值**。
//
// ★ 关键的一步：**「最大值的最小值」⇒ 二分那个最大值**（第 9 章那一整章）。
//   固定一个上限 mid 之后，题目当场塌成一句话：
//       只准走过路费 f[i] ≤ mid 的城市，问 1 → n 的最短（掉血）路是不是 ≤ b。
//   —— 而这一问，正是本章的 Dijkstra。
//
//   ⇒ 二分 + Dijkstra，`O(m log n × log V)`。这是第 9 章那套二分答案在图上的第一次登场。
//
// ★ 单调性（二分的前提）为什么成立：mid 越大，能走的城市**只多不少** ⇒ 最短路只会更短
//   ⇒ 「可行」一旦成立，往上就一直成立。度量程序把**所有阈值逐个试了一遍**，
//     300 轮全都是「一串 0 之后全是 1」，没有一轮跳来跳去（第 9 章那条：单调性要验，不能默认）。
//
// ⚠ 三处一不小心就写错的地方，各配了一份错误版本：
//   ① **过路费包括起点和终点** —— f[1] 和 f[n] 也要 ≤ mid（p1462NoEnd.cpp）；
//   ② 「血量降低至**负数**才不行」⇒ 判据是 `dist <= b`，**不是** `dist < b`（p1462Strict.cpp）；
//   ③ 掉血总和：路径最多 n−1 = 10⁴ 条边、每条 10⁹ ⇒ **10¹³**，必须 long long（p1462Int.cpp）。
//
// ⚠ 答案一定是某个 f[i]（它就是路径上的某个点的费用），所以二分**在排序去重后的 f 值上做**。

#include <bits/stdc++.h>
using namespace std;
typedef long long ll;
typedef pair<ll, int> PLI;

const ll INF = (ll)4e18;

int n, m;
ll b;
vector<int> f;
vector<vector<pair<int, int>>> g;

/* 只准走 f[i] <= lim 的城市，问 1 → n 的最短掉血是多少 */
static ll shortest(int lim) {
    if (f[1] > lim || f[n] > lim) return INF;       // ★ 起点和终点也要交钱
    vector<ll> dist(n + 1, INF);
    priority_queue<PLI, vector<PLI>, greater<PLI>> q;
    dist[1] = 0;
    q.push({0, 1});
    while (!q.empty()) {
        auto [d, u] = q.top();
        q.pop();
        if (d > dist[u]) continue;
        for (auto [v, w] : g[u]) {
            if (f[v] > lim) continue;               // 这座城市交不起，绕开
            if (d + w < dist[v]) { dist[v] = d + w; q.push({dist[v], v}); }
        }
    }
    return dist[n];
}

int main() {
    ios::sync_with_stdio(false);
    cin.tie(nullptr);

    if (!(cin >> n >> m >> b)) return 0;
    f.assign(n + 1, 0);
    for (int i = 1; i <= n; i++) cin >> f[i];
    g.assign(n + 1, {});
    for (int i = 0; i < m; i++) {
        int u, v, w;
        cin >> u >> v >> w;
        g[u].push_back({v, w});
        g[v].push_back({u, w});                     // 题面：双向公路
    }

    vector<int> cand(f.begin() + 1, f.end());
    sort(cand.begin(), cand.end());
    cand.erase(unique(cand.begin(), cand.end()), cand.end());

    int lo = 0, hi = (int)cand.size() - 1, ans = -1;
    while (lo <= hi) {                              // 二分「最大值」的那个下标
        int mid = (lo + hi) / 2;
        if (shortest(cand[mid]) <= b) { ans = cand[mid]; hi = mid - 1; }   // ★ <= 不是 <
        else lo = mid + 1;
    }
    if (ans < 0) cout << "AFK\n";
    else cout << ans << '\n';
    return 0;
}

// ✗ 错法①：只限制**中间**的城市，忘了「过路费包括起点和终点」
//
// 题面原话：「每次经过一个城市，都会被收取一定的过路费（**包括起点和终点**）。」
// 那半句括号是出题人专门加的，而顺手写 check 时最容易只写「走到 v 之前看一眼 f[v]」，
// 结果 f[1] 和 f[n] 谁也没查。
//
// ★ 它的方向是可判的：少了两个限制 ⇒ 可行的 mid 只多不少 ⇒ **答案恒 ≤ 正解**
//   （[第 26 章那条判据](/sol/p1220/)：解的是一个放宽了的问题）。300 轮实测一次没反过来。
//
// ⚠ 而官方样例**当场就挡住它**：那组数据里起点 f[1] = 8、终点 f[4] = 10，
//   正解就是被终点顶上去的 10，而这一版只看中间那个 5。

#include <bits/stdc++.h>
using namespace std;
typedef long long ll;
typedef pair<ll, int> PLI;

const ll INF = (ll)4e18;

int n, m;
ll b;
vector<int> f;
vector<vector<pair<int, int>>> g;

static ll shortest(int lim) {
    /* ⚠ 少的就是这两句：if (f[1] > lim || f[n] > lim) return INF; */
    vector<ll> dist(n + 1, INF);
    priority_queue<PLI, vector<PLI>, greater<PLI>> q;
    dist[1] = 0;
    q.push({0, 1});
    while (!q.empty()) {
        auto [d, u] = q.top();
        q.pop();
        if (d > dist[u]) continue;
        for (auto [v, w] : g[u]) {
            if (v != n && f[v] > lim) continue;     // ⚠ 连终点都放行了
            if (d + w < dist[v]) { dist[v] = d + w; q.push({dist[v], v}); }
        }
    }
    return dist[n];
}

int main() {
    ios::sync_with_stdio(false);
    cin.tie(nullptr);
    if (!(cin >> n >> m >> b)) return 0;
    f.assign(n + 1, 0);
    for (int i = 1; i <= n; i++) cin >> f[i];
    g.assign(n + 1, {});
    for (int i = 0; i < m; i++) {
        int u, v, w;
        cin >> u >> v >> w;
        g[u].push_back({v, w});
        g[v].push_back({u, w});
    }
    vector<int> cand(f.begin() + 1, f.end());
    sort(cand.begin(), cand.end());
    cand.erase(unique(cand.begin(), cand.end()), cand.end());
    int lo = 0, hi = (int)cand.size() - 1, ans = -1;
    while (lo <= hi) {
        int mid = (lo + hi) / 2;
        if (shortest(cand[mid]) <= b) { ans = cand[mid]; hi = mid - 1; }
        else lo = mid + 1;
    }
    if (ans < 0) cout << "AFK\n";
    else cout << ans << '\n';
    return 0;
}

// ✗ 错法②：血量判据写成 `dist < b`（严格小于）
//
// 题面原话：「他的血量最多为 b，出发时他的血量是满的。**如果他的血量降低至负数，
// 则他就无法到达奥格瑞玛。**」
//
// ⇒ 掉血正好等于 b 时，血量是 **0**，**0 不是负数** ⇒ 这条路**是可行的**。
//   判据必须是 `dist <= b`。
//
// ⚠ 这是一个只在**一条线上**才现形的 off-by-one：触发条件是「最短掉血恰好等于 b」。
//   ⇒ 顺手随机（b 从一个大范围里抽）几乎撞不上；
//     ★ 而把 b **对齐到某条真实路径的长度**上，它当场 300 / 300 全错（生成器档位 1）。
//   ⇒ 又一次「[边界要跨过那条具体的线](/sol/p1182/)」：这条线不是「大概附近」，是**恰好那一个值**。

#include <bits/stdc++.h>
using namespace std;
typedef long long ll;
typedef pair<ll, int> PLI;

const ll INF = (ll)4e18;

int n, m;
ll b;
vector<int> f;
vector<vector<pair<int, int>>> g;

static ll shortest(int lim) {
    if (f[1] > lim || f[n] > lim) return INF;
    vector<ll> dist(n + 1, INF);
    priority_queue<PLI, vector<PLI>, greater<PLI>> q;
    dist[1] = 0;
    q.push({0, 1});
    while (!q.empty()) {
        auto [d, u] = q.top();
        q.pop();
        if (d > dist[u]) continue;
        for (auto [v, w] : g[u]) {
            if (f[v] > lim) continue;
            if (d + w < dist[v]) { dist[v] = d + w; q.push({dist[v], v}); }
        }
    }
    return dist[n];
}

int main() {
    ios::sync_with_stdio(false);
    cin.tie(nullptr);
    if (!(cin >> n >> m >> b)) return 0;
    f.assign(n + 1, 0);
    for (int i = 1; i <= n; i++) cin >> f[i];
    g.assign(n + 1, {});
    for (int i = 0; i < m; i++) {
        int u, v, w;
        cin >> u >> v >> w;
        g[u].push_back({v, w});
        g[v].push_back({u, w});
    }
    vector<int> cand(f.begin() + 1, f.end());
    sort(cand.begin(), cand.end());
    cand.erase(unique(cand.begin(), cand.end()), cand.end());
    int lo = 0, hi = (int)cand.size() - 1, ans = -1;
    while (lo <= hi) {
        int mid = (lo + hi) / 2;
        if (shortest(cand[mid]) < b) { ans = cand[mid]; hi = mid - 1; }   // ⚠ 少了一个等号
        else lo = mid + 1;
    }
    if (ans < 0) cout << "AFK\n";
    else cout << ans << '\n';
    return 0;
}

// ✗ 错法③：忘了「双向公路」，每条边只存一遍
//
// 题面：「城市之间有 m 条**双向**的公路」。
//
// ⇒ ★★★ 这一章的题单把同一行代码演了**三遍，而且结论各不相同**：
//     [P1339](/sol/p1339/)（无向图）：`g[v].push_back(...)` —— **必须写**；
//     [P1629](/sol/p1629/)（单行道）：写了它**当场就错**；
//     P1462（双向公路）：**又必须写**。
//   ⇒ 「存一遍还是两遍」不是一个能背的习惯，是**每道题读一次题面**的事
//     （第 52 章那条「上一章的正确写法就是这一章的 bug」，在同一张题单里演到了第三次）。
//
// ★ 它的方向可判：边少了一半 ⇒ 路只会更长、可行的阈值只会更少 ⇒ **答案恒 ≥ 正解**
//   （走不通就是 AFK，那是「最大」的那一端）。

#include <bits/stdc++.h>
using namespace std;
typedef long long ll;
typedef pair<ll, int> PLI;

const ll INF = (ll)4e18;

int n, m;
ll b;
vector<int> f;
vector<vector<pair<int, int>>> g;

static ll shortest(int lim) {
    if (f[1] > lim || f[n] > lim) return INF;
    vector<ll> dist(n + 1, INF);
    priority_queue<PLI, vector<PLI>, greater<PLI>> q;
    dist[1] = 0;
    q.push({0, 1});
    while (!q.empty()) {
        auto [d, u] = q.top();
        q.pop();
        if (d > dist[u]) continue;
        for (auto [v, w] : g[u]) {
            if (f[v] > lim) continue;
            if (d + w < dist[v]) { dist[v] = d + w; q.push({dist[v], v}); }
        }
    }
    return dist[n];
}

int main() {
    ios::sync_with_stdio(false);
    cin.tie(nullptr);
    if (!(cin >> n >> m >> b)) return 0;
    f.assign(n + 1, 0);
    for (int i = 1; i <= n; i++) cin >> f[i];
    g.assign(n + 1, {});
    for (int i = 0; i < m; i++) {
        int u, v, w;
        cin >> u >> v >> w;
        g[u].push_back({v, w});                 // ⚠ 只存了一遍
    }
    vector<int> cand(f.begin() + 1, f.end());
    sort(cand.begin(), cand.end());
    cand.erase(unique(cand.begin(), cand.end()), cand.end());
    int lo = 0, hi = (int)cand.size() - 1, ans = -1;
    while (lo <= hi) {
        int mid = (lo + hi) / 2;
        if (shortest(cand[mid]) <= b) { ans = cand[mid]; hi = mid - 1; }
        else lo = mid + 1;
    }
    if (ans < 0) cout << "AFK\n";
    else cout << ans << '\n';
    return 0;
}

// ★ 「掉血用 int、INF 写 0x3f3f3f3f」—— ⚠⚠ 我的草稿说它会溢出，**实测它恰好是对的**
//
// 草稿里的理由听着很顺：一条路径最多 n−1 = 9999 条边、每条 c ≤ 10⁹
//   ⇒ 掉血总和能到 10¹³，int 只到 2 147 483 647 —— 差 4657 倍，必炸。
//
// **这个推理错在「哪一个量真的会被算出来」。** 两行就能证它安全：
//
//   ① 只有 `nd < dist[v]` 时才写进 dist，而 dist 的初值是 INF = 0x3f3f3f3f
//      ⇒ **dist 里存下来的值永远 < 1 061 109 567**；
//   ② 于是每一次加法都是「一个 < 1 061 109 567 的数」＋「一条 ≤ 10⁹ 的边」
//      ⇒ 最大 **2 061 109 566** < 2 147 483 647。★ **余量 4.0%，一次都不会溢出。**
//
//   ★ 而「答案会不会因此错」也是同一条推理：题面 b ≤ 10⁹，
//     所以任何**可行**路径的掉血 ≤ 10⁹ < 0x3f3f3f3f —— 有用的距离一个都没被 INF 拦住。
//
// ⇒ 这是「[答案 ≥ 任何一个被用到的中间值](/sol/p1164/)」那条论证模式在本章的第三次，
//   而这一章的三道题把它的三种结局凑齐了：
//     [P3371] Σw < 2³¹ ⇒ **不够**（差 2.02 倍，300 / 300 全错）
//     [P4779] Σw ≤ 10⁹ ⇒ **恰好够**（余量 6.1%）
//     P1462   b ≤ 10⁹  ⇒ **恰好够**（余量 4.0%）
//   ⇒ ★★ **「要不要 long long」永远是一道拿这道题的题面乘一遍的算术题，没有通用答案。**
//
// ⚠ 但结论不是「就该写 int」：4.0% 的余量意味着题面改一个字它就塌了。
//   正解仍然用 long long —— **不必去记那 4.0%。**

#include <bits/stdc++.h>
using namespace std;
typedef pair<int, int> PII;

const int INF = 0x3f3f3f3f;

int n, m;
long long b;
vector<int> f;
vector<vector<PII>> g;

static int shortest(int lim) {
    if (f[1] > lim || f[n] > lim) return INF;
    vector<int> dist(n + 1, INF);
    priority_queue<PII, vector<PII>, greater<PII>> q;
    dist[1] = 0;
    q.push({0, 1});
    while (!q.empty()) {
        auto [d, u] = q.top();
        q.pop();
        if (d > dist[u]) continue;
        for (auto [v, w] : g[u]) {
            if (f[v] > lim) continue;
            if (d + w < dist[v]) { dist[v] = d + w; q.push({dist[v], v}); }
        }
    }
    return dist[n];
}

int main() {
    ios::sync_with_stdio(false);
    cin.tie(nullptr);
    if (!(cin >> n >> m >> b)) return 0;
    f.assign(n + 1, 0);
    for (int i = 1; i <= n; i++) cin >> f[i];
    g.assign(n + 1, {});
    for (int i = 0; i < m; i++) {
        int u, v, w;
        cin >> u >> v >> w;
        g[u].push_back({v, w});
        g[v].push_back({u, w});
    }
    vector<int> cand(f.begin() + 1, f.end());
    sort(cand.begin(), cand.end());
    cand.erase(unique(cand.begin(), cand.end()), cand.end());
    int lo = 0, hi = (int)cand.size() - 1, ans = -1;
    while (lo <= hi) {
        int mid = (lo + hi) / 2;
        if (shortest(cand[mid]) <= b) { ans = cand[mid]; hi = mid - 1; }
        else lo = mid + 1;
    }
    if (ans < 0) cout << "AFK\n";
    else cout << ans << '\n';
    return 0;
}