题面
解析
题面直接说了最大值最小，二分无疑
看到这题的应该都想到了最短路吧，但是一看又要管花费，还要管血量立马慌了，但是其实没有那么复杂
二分歪嘴哦经过城市单次交费最大值\(x\)（不是等会代码的x，这里只是便于书写），通过 Dijkstra算法 得到对于这个\(x\)的最小耗血，\(x\)越大能走的路一定不会变少，耗血自然不会少，等到能活下来且\(x\)最小，答案就出来了
代码
会被hack的代码，\(WA\), \(100pts\)
#include <bits/stdc++.h>using namespace std;constexpr int N = 5e4 + 2;int n, m, b;
int v[N], d[N];
bool f[N];
vector<pair<int, int>> a[N];inline void read() {cin >> n >> m >> b;for (int i = 1; i <= n; i++) {cin >> v[i];}for (int i = 1; i <= m; i++) {int u, v, w;cin >> u >> v >> w;a[u].push_back({v, w});a[v].push_back({u, w});}
}inline bool check(int mx) {for (int k = 1; k <= N; k++) {d[k] = (1 << 30);}memset(f, 0, sizeof f);priority_queue<pair<int, int>, vector<pair<int, int>>, greater<pair<int, int>>> q;q.push({0, 1});d[1] = 0;while (!q.empty()) {auto t = q.top();q.pop();int now = t.second;if (f[now]) continue;f[now] = true;for (auto i : a[now]) {int x = i.first, y = i.second;if (v[x] > mx) continue;if (d[x] > d[now] + y) {d[x] = d[now] + y;q.push({d[x], x});}}}int mi = d[n];if (b - mi >= 0)return true;elsereturn false;
}signed main() {ios::sync_with_stdio(false);cin.tie(nullptr);read();int l = 0, r = 1e9;int ans = -1;while (l <= r) {int mid = (l + r) / 2;if (check(mid))r = mid - 1, ans = mid;elsel = mid + 1;}if (ans == -1)cout << "AFK";elsecout << ans;return 0;
}
关于hack
上面的代码，没有考虑原点是否会超收费！
\(AC\),\(100pts\)
#include <bits/stdc++.h>using namespace std;constexpr int N = 5e4 + 2;
#define int long longint n, m, b;
int v[N], d[N];
bool f[N];
vector<pair<int, int>> a[N];inline void read() {cin >> n >> m >> b;for (int i = 1; i <= n; i++) {cin >> v[i];}for (int i = 1; i <= m; i++) {int u, v, w;cin >> u >> v >> w;a[u].push_back({v, w});a[v].push_back({u, w});}
}inline bool check(int mx) {if (v[1] > mx) return false;for (int k = 1; k <= N; k++) {d[k] = (1 << 30);}memset(f, 0, sizeof f);priority_queue<pair<int, int>, vector<pair<int, int>>, greater<pair<int, int>>> q;q.push({0, 1});d[1] = 0;while (!q.empty()) {auto t = q.top();q.pop();int now = t.second;if (f[now]) continue;f[now] = true;for (auto i : a[now]) {int x = i.first, y = i.second;if (v[x] > mx) continue;if (d[x] > d[now] + y) {d[x] = d[now] + y;q.push({d[x], x});}}}int mi = d[n];if (b - mi >= 0)return true;elsereturn false;
}signed main() {ios::sync_with_stdio(false);cin.tie(nullptr);read();int l = 0, r = 1e9;int ans = -1;while (l <= r) {int mid = (l + r) / 2;if (check(mid))r = mid - 1, ans = mid;elsel = mid + 1;}if (ans == -1)cout << "AFK";elsecout << ans;return 0;
}
看懂？点赞？