博客
关于我
强烈建议你试试无所不能的chatGPT,快点击我
1462 通往奥格瑞玛的道路
阅读量:5859 次
发布时间:2019-06-19

本文共 2093 字,大约阅读时间需要 6 分钟。

 P1462 通往奥格瑞玛的道路

题目背景

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

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

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

题目描述

在艾泽拉斯,有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。

 

输入输出样例

输入样例#1: 
4 4 8856102 1 22 4 11 3 43 4 3
输出样例#1: 
10

说明

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

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

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

 

 

这个题的要求是真的绕,看了一半天被这个'最多的一次收取的费用的最小值'给绕的晕乎乎的,原来是要我们在能从起点到终点的前提下,所经过城市花费的单个过路费最大值的最小值

思路就是二分枚举一下单次花费的最值,直到再减少花费就不能到达终点为止。

 

1 #include
2 #include
3 #include
4 #include
5 #include
6 using namespace std; 7 typedef long long LL; 8 const LL INF = 900000000; 9 const int maxn = 1e4+10;10 struct node{11 LL to,cost;12 };13 vector
e[maxn];14 LL dis[maxn],f[maxn],a[maxn],k[maxn];15 bool vis[maxn];16 LL n,m,b;17 bool SPFA(LL key)18 {19 if(a[1]>key)return false;20 for(int i=0;i
Q;28 Q.push(1);29 while(!Q.empty()){30 LL t = Q.front();Q.pop();31 vis[t] = false;32 for(int i=0;i
dis[t]+e[t][i].cost){35 dis[tmp] = dis[t] +e[t][i].cost;36 if(!vis[tmp]&&k[tmp]<=key){37 vis[tmp] = true;38 Q.push(tmp);39 if(++f[tmp]>n)return false;40 }41 }42 }43 }44 if(dis[n]
>n>>m>>b){51 LL l = 0,r = 0;52 for(int i=1;i<=n;i++){53 cin>>k[i];54 r = max(r,k[i]);// 缴费肯定不会大于收费最大值55 }56 l = max(k[1],k[n]);//缴费肯定不会小与起点或终点57 LL x,y,z;58 for(int i=0;i
>x>>y>>z;60 if(x==y)continue;61 node q;62 q.to = y;63 q.cost = z;64 e[x].push_back(q);65 q.to = x;66 e[y].push_back(q);67 }68 if(!SPFA(INF)){//如果在没有过路费限制的情况下都不能到达终点,则直接输出不能到达69 cout<<"AFK"<
>1;74 if(SPFA(mid))r = mid-1;75 else l = mid+1;76 }77 cout<
<

 

转载于:https://www.cnblogs.com/wangrunhu/p/9431398.html

你可能感兴趣的文章
基于 Nest.js (nodejs 版的 spring ) 的 Notadd 2.0 Beta1 发布
查看>>
巧用这19条MySQL优化,效率至少提高3倍
查看>>
交换两个变量的骚操作
查看>>
React 出海应用 首屏加载时间从20S降到10S以下 血泪史
查看>>
promise的用法以及注意事项,看了这篇你就会了
查看>>
阿里云 Aliplayer高级功能介绍(八):安全播放
查看>>
从0到1快速构建基于create-react-app的脚手架
查看>>
【零基础】计算机网络技术
查看>>
Android进程间的通信 IPC(机制)Binder的原理和源码阅读
查看>>
Android之ContentObserver内容观察者的使用
查看>>
看完这个,Java IO从此不在难
查看>>
基于django的视频点播网站开发-step3-注册登录功能
查看>>
为什么通信企业都要主动拥抱百度AI?
查看>>
并发-7-同步容器和ConcurrentHashMap
查看>>
BigDecimal类
查看>>
Redis 集合和有序集合
查看>>
http请求头与响应头的应用
查看>>
零基础学习 Python 之列表
查看>>
使用leancloud实现迭代查询
查看>>
事件循环(the Event Loop)、宏任务(macrotask)、微任务(microtask)
查看>>