南宁月嫂网站建设,邢台高端网站建设,最近高清中文在线国语字幕,广州新公司网站建设在艾泽拉斯大陆上有一位名叫歪嘴哦的神奇术士#xff0c;他是部落的中坚力量有一天他醒来后发现自己居然到了联盟的主城暴风城在被众多联盟的士兵攻击后#xff0c;他决定逃回自己的家乡奥格瑞玛 题目背景【题目描述#xff1a;】 在艾泽拉斯#xff0c;有n个城市。编号为1… 在艾泽拉斯大陆上有一位名叫歪嘴哦的神奇术士他是部落的中坚力量有一天他醒来后发现自己居然到了联盟的主城暴风城在被众多联盟的士兵攻击后他决定逃回自己的家乡奥格瑞玛 题目背景 【题目描述】 在艾泽拉斯有n个城市。编号为1,2,3,...,n。 城市之间有m条双向的公路连接着两个城市从某个城市到另一个城市会遭到联盟的攻击进而损失一定的血量。 每次经过一个城市都会被收取一定的过路费包括起点和终点。路上并没有收费站。 假设1为暴风城n为奥格瑞玛而他的血量最多为b出发时他的血量是满的。 歪嘴哦不希望花很多钱他想知道在可以到达奥格瑞玛的情况下他所经过的所有城市中最多的一次收取的费用的最小值是多少。 【输入格式】 第一行3个正整数nmb。分别表示有n个城市m条公路歪嘴哦的血量为b。 接下来有n行每行1个正整数fi。表示经过城市i需要交费fi元。 再接下来有m行每行3个正整数aibici(1aibin)。表示城市ai和城市bi之间有一条公路如果从城市ai到城市bi或者从城市bi到城市ai会损失ci的血量。 【输出格式】 仅一个整数表示歪嘴哦交费最多的一次的最小值。 如果他无法到达奥格瑞玛输出AFK。 输入样例#1
4 4 8
8
5
6
10
2 1 2
2 4 1
1 3 4
3 4 3
输出样例#1
10 输入输出样例 【算法分析】 问题可以看作 给定一张图给定边权和点权给定一个最大边权 问从点1到点n的路径的总长度不大于最大边权时点权的最大值最小 假设一个最大值问题就变成了 求出一条经过的点的点权都不大于这个最大值的最短路径并且这条最短路的长度小于最大边权生命值为0就GG了 好像可以二分答案证一证它的单调性 当一个数num被选为最大值的时候如果存在一条“经过的点的点权都不大于这个最大值的最短路径并且这条最短路的长度小于最大边权” 则num可以选为最大值。 当num变小时可以经过的城市变少可选的点数变少受到的伤害便可能增多 使受到的伤害尽可能大但不能超过总生命值最大的点权值就会尽可能小 故num不一定是最优解所以从[l, mid]内寻找解 当num作为最大值过小时就要从[mid 1, r]中寻找解. 也就是说这道题将伤害视作边权二分点权最大值跑最短路松弛的条件多加了一个松弛的点的点权必须小于最大点权 每次跑完最短路后如果受到的伤害小于血量那么这个最大点权便是一个解. 【代码】 1 //通往奥格瑞玛的道路2 #includeiostream3 #includecstdio4 #includecstring5 using namespace std;6 7 const int MAXN 10000 1;8 const int MAXM 50000 1;9 const int INF 0x3f3f3f3f;
10
11 int n, m, blood;
12 int city[MAXN];
13
14 int edge_num, head[MAXN];
15 struct edge {
16 int len, to, next;
17 }h[MAXM * 2];
18
19 inline void Add(int from, int to, int len) {
20 h[edge_num].next head[from];
21 h[edge_num].to to, h[edge_num].len len;
22 head[from] edge_num;
23 }
24
25 inline int read() {
26 int x 0; char ch getchar();
27 while(ch 0 || ch 9) ch getchar();
28 while(ch 0 ch 9)
29 x (x 3) (x 1) ch - 48, ch getchar();
30 return x;
31 }
32
33 int fro, rear;
34 int dis[MAXN], que[MAXN * 20];
35 bool in_que[MAXN];
36 void SPFA(int money) {
37 for(int i 0; i n; i) dis[i] INF;
38 memset(in_que, 0, sizeof(in_que));
39 in_que[1] 1, dis[1] 0;
40 que[fro rear 1] 1;
41 while(fro rear) {
42 int x que[fro];
43 in_que[x] 0;
44 for(int i head[x]; i; i h[i].next) {
45 int l h[i].len, y h[i].to;
46 if(dis[x] l dis[y] city[y] money) {
47 dis[y] dis[x] l;
48 if(!in_que[y]) in_que[y] 1, que[rear] y;
49 }
50 }
51 }
52 }
53
54 inline bool check(int money) {
55 SPFA(money);
56 return dis[n] blood;
57 }
58 int main() {
59 int l 0, r 0;
60 n read(), m read(), blood read();
61 for(int i 1; i n; i) {
62 city[i] read();
63 r max(r, city[i]);
64 }
65 l max(city[1], city[n]);
66 for(int i 1; i m; i) {
67 int a, b, c;
68 a read(), b read(), c read();
69 if(a ! b) {
70 Add(a, b, c);
71 Add(b, a, c);
72 }
73 }
74 if(!check(r)) { puts(AFK); return 0; }
75 while(l r) {
76 int mid (l r) 1;
77 if(!check(mid)) l mid 1;
78 else r mid - 1;
79 }
80 printf(%d\n, l);
81 } 转载于:https://www.cnblogs.com/devilk-sjj/p/9042030.html
