通往奥格瑞玛的道路 最短路的综合应用

zz/2024/5/21 21:41:35

通往奥格瑞玛的道路

题目链接

通往奥格瑞玛的道路

题目描述

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

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

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

在艾泽拉斯,有n个城市。编号为1,2,3,…,n。

城市之间有m条双向的公路,连接着两个城市,从某个城市到另一个城市,会遭到联盟的攻击,进而损失一定的血量。

每次经过一个城市,都会被收取一定的过路费(包括起点和终点)。路上并没有收费站。

假设1为暴风城,n为奥格瑞玛,而他的血量最多为b,出发时他的血量是满的。

歪嘴哦不希望花很多钱,他想知道,在可以到达奥格瑞玛的情况下,他所经过的所有城市中最多的一次收取的费用的最小值是多少。

输入

第一行3个正整数,n,m,b。分别表示有n个城市,m条公路,歪嘴哦的血量为b。
接下来有n行,每行1个正整数,fi。表示经过城市i,需要交费fi元。
再接下来有m行,每行3个正整数,ai,bi,ci(1<=ai,bi<=n)。表示城市ai和城市bi之间有一条公路,如果从城市ai到城市bi,或者从城市bi到城市ai,会损失ci的血量。

输出

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

样例输入

4 4 8
8
5
6
10
2 1 2
2 4 1
1 3 4
3 4 3

样例输出

10

说明/提示

对于60%的数据,满足n≤200,m≤10000,b≤200

对于100%的数据,满足n≤10000,m≤50000,b≤1000000000

对于100%的数据,满足ci≤1000000000,fi≤1000000000,可能有两条边连接着相同的城市。

题目分析

窝觉得作为一道蓝题,这题的难度实在是太水了。。。

图论问题的难点一般都在建图上,本题的一个限制条件是歪嘴哦同学的血量,所以我们可以把每条路损失的血量定为边权值s,起始点的状态为0,求到达n点时的最小值,就可以转换为一个简单的最短路问题。如果到达终点时歪嘴哦同学的消耗值达到了b,那么就返回false。

题目要求的是输出歪嘴哦同学交费最多的一次的最小值,在最短路问题的综合应用中,大多数类似的问题都可以用二分来解决,因为答案就是这条路上最大的交费,所以我们可以记录交费的最大值和最小值,然后进行二分搜索,如果在这个范围内,歪嘴哦同学走到n点的消耗小于b值,那么代表这个范围可以,范围上升,反之向下。

根据这道题的数据范围,可以用领接表存储这张图,二分搭配sfpa进行判断即可,题目要求如果他无法到达奥格瑞玛,输出AFK,其实就是在没有交费限制的条件下,歪嘴哦同学走到n点的消耗大于b,所以在二分之前可以判断一下

代码如下

#include <iostream>
#include <cstring>
#include <queue>
#include <algorithm>using namespace std;
const int N = 10010,M = 50010;
int h[N],ne[M * 2],e[M * 2],s[M * 2],idx;
int mon[N];
int backup[N];
int d[N];
bool st[N];
int n,m,b;void add(int x,int y,int z){ne[idx] = h[x];e[idx] = y;s[idx] = z;h[x] = idx++;
}bool spfa(int mid){memset(d,0x3f,sizeof d);queue<int> Q;d[1] = 0;Q.push(1);st[1] = true;while(Q.size()){int t = Q.front();Q.pop();st[t] = false;for(int i = h[t];i != -1;i = ne[i]){int j = e[i];if(mon[j] > mid) continue;if(d[j] > d[t] + s[i]){d[j] = d[t] + s[i];if(!st[j]) Q.push(j);}}}if(d[n] >= b) return false;else return true;
}int main(){memset(h,-1,sizeof h);cin >> n >> m >> b;int l = 1,r = n;for(int i = 1;i <= n;i++){cin >> mon[i];backup[i] = mon[i];}while(m--){int x,y,z;cin >> x >> y >> z;add(x,y,z),add(y,x,z);}sort(backup + 1,backup + 1 + n);if(!spfa(backup[n])){cout << "AFK" << endl;return 0;}int ans = 0x3f3f3f3f;while(l < r){int mid = (l + r + 1) >> 1;memset(st,0,sizeof st);if(spfa(backup[mid])) r = mid - 1,ans = min(ans,backup[mid]);else l = mid;}if(ans == 0x3f3f3f3f) cout << "AFK" << endl;else cout << ans << endl;
}

http://www.ngui.cc/zz/2727392.html

相关文章

B. Array Walk

传送门 分析 这题的题意大概就是有1-n个点&#xff0c;每个点赋值为a[i]&#xff0c;现在可以移动k次&#xff0c;不过只能向左移动z次&#xff0c;并且不能连续向左移动&#xff0c;问你最后走过所有点的和最大是多少 这题很明显思路是一个dp&#xff0c;但是怎么进行状态转…

Codeforces 954E:Water Taps 贪心

传送门 题目描述 ∀ x i ∈ [ 1 , a i ] , \forall x_i\in[1,a_i], ∀xi​∈[1,ai​],对于所有满足 ∑ i 1 n x i ( t i − T ) 0 \sum_{i1}^nx_i(t_i-T)0 ∑i1n​xi​(ti​−T)0的情况,求 ∑ i 1 n x i \sum_{i1}^nx_i ∑i1n​xi​的最大值 分析 我们可以计算大于m和小…

CodeForces 792C :Divide by Three DP + 路径还原

传送门 题目描述 在一个黑板上写着一个正整数 n 。它有不超过10^5位&#xff08;话说黑板上是怎么写下这个数的&#xff09; 。老师给你了一个任务&#xff0c;把它魔改成一个 美丽数 &#xff0c;而且因为你很懒&#xff0c;你非常非常的想用最小的步数把它改成一个 美丽数 …

CodeForces 372C :Watching Fireworks is Fun DP + 单调队列

传送门 题目描述 给出N个位子&#xff0c;排成一列&#xff0c;现在有M个烟花&#xff0c;每秒人的速度d&#xff0c;每个烟花有三个元素&#xff1a;a&#xff0c;b&#xff0c;t&#xff0c;表示在时刻t会绽放&#xff0c;如果我们在位子x观看到了的话&#xff0c;会获得b-…

CodeForces 961D:Pair Of Lines 思维

传送门 题目描述 在平面直角坐标系上给出n个点&#xff0c;求是否存在两条直线穿过所有点。 分析 前面三个点中&#xff0c;任意两个点必成一条直线&#xff0c;所以我们去枚举三个点中的两个&#xff0c;然后去判断其他的点是否在这条直线上&#xff0c;然后再判断不在这条…

CodeForces 319B :Psychos in a Line 单调栈

传送门 题目描述 有编号为1~N的N个人站成一排&#xff08;顺序是乱的&#xff09;&#xff0c;每人手中拿着一把枪。每一个时刻&#xff0c;每个人同时瞄准右边的人&#xff08;如果存在的话&#xff09;&#xff0c;然后如果这个人编号比自己大&#xff0c;则开枪将他打死。…

Wireless Password :ac自动机 + 状压DP

分析 f[i][j][k]表示第i位的情况下&#xff0c;在trie图上的位置位j的情况下匹配情况位k&#xff0c;状态转移方程就比较好写了 dp[i 1][tr[j][c]][l | cnt[tr[j][c]]] (dp[i 1][tr[j][c]][l | cnt[tr[j][c]]] dp[i][j][l]) % mod注意一下减去不合法的状态&#xff0c;节…

CodeForces 1367E :Necklace Assembly 思维

传送门 题目描述 给你一个字符串&#xff0c;你从中挑选一些让它们成为一个环&#xff0c;使得这个环朝一个方向转 k k k下&#xff0c;与原来看起来一样&#xff0c;找到你能够满足这个条件的可以挑选的最多的字符数量。 分析 我们去枚举 k k k的因子&#xff0c;那么我转…

POJ - 3635 :Full Tank? 最短路 + 拆点

分析 跟前段时间看的一个拆点求邻接矩阵快速幂的一个题有点像 这个题比较朴素的方法就是我把每个点剩余 j j j单位的汽油的最低花费处理出来&#xff0c;然后这样写毫无疑问会tle&#xff0c;所以我们需要去进行一些优化 首先我们思考一下这个朴素的思想为什么会超时&#xff…

CodeForces 546E :Soldier and Traveling 网络流 +拆点

传送门 题目描述 题意大概就是给定 n n n 个城市&#xff0c; m m m 条边。 然后人只能从走相邻边相连的城市。 现在给你初始城市的每一个人数&#xff0c;再给一组每个城市人数。询问是否可以从当前人数变换到给定人数。如果能&#xff0c;输入“YES”并输出方案&#xff0…