2025年【洛谷】P1462 通往奥格瑞玛的道路

大家好，我是讯享网，很高兴认识大家。

题目地址：

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

题目描述：
在艾泽拉斯，有 $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。

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

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

#include <iostream> #include <cstring> #include <queue> using namespace std; using PLI = pair<long, int>; const int N = 10010, M = ; 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); }

讯享网

时间复杂度 $O(m\log n\log (R-L))$ ， $L=\max\{f_1,f_n\}, R=\max_i f_i$ ，空间 $O (n + m)$ 。

2025年【洛谷】P1462 通往奥格瑞玛的道路

题目地址：

相关推荐