hhoppitree @ 2021-01-20 20:55:49
### 题目背景
在艾泽拉斯大陆上有一位名叫歪嘴哦的神奇术士，他是部落的中坚力量。
有一天他醒来后，发现自己居然到了联盟的主城暴风城。
在被众多联盟的士兵攻击后，他决定逃回自己的家乡奥格瑞玛。
### 题目描述
在艾泽拉斯，有 $n$ 个城市，编号为 $1,2,3,\cdots,n$。
城市之间有 $m$ 条双向的公路，连接着两个城市，从某个城市到另一个城市，会遭到联盟的攻击，进而损失一定的血量。
每次经过一个城市，都会被收取一定的过路费（包括起点和终点），路上并没有收费站。
假设 $1$ 为暴风城，$n$ 为奥格瑞玛，而他的血量最多为 $b$，出发时他的血量是满的。
歪嘴哦不希望花很多钱，他想知道，在可以到达奥格瑞玛的情况下，他所经过的所有城市中最多的一次收取的费用的最小值是多少。
### 输入格式
第一行三个正整数 $n,m,b$，分别表示有 $n$ 个城市，$b$ 条公路，歪嘴哦的血量为 $b$。
接下来有 $n$ 行，每行一个正整数 $f_i$，表示经过城市 $i$，需要交费 $f_i$ 元。
再接下来有 $m$ 行，每行三个正整数 $a_i,b_i,c_i$。表示城市 $a_i$ 和城市 $b_i$ 之间有一条双向公路，如果从城市 $a_i$ 到城市 $b_i$，或者从城市 $b_i$ 到城市 $a_i$，会损失 $c_i$ 的血量。
### 输出格式
仅一个整数，表示歪嘴哦交费最多的一次的最小值。
如果他无法到达奥格瑞玛，输出 ```AFK```。
### 说明/提示
对于 $60\%$ 的数据，满足 $n\le200,m\le10^4,b\le200$；
对于 $100\%$ 的数据，满足 $1\le n\le10^4,1\le m\le5\times 10^4,1\le b,f_i,c_i\le10^9,1\le a_i,b_i\le n$。
**不保证不存在重边或自环。**
by hhoppitree @ 2021-01-20 20:56:02
在艾泽拉斯大陆上有一位名叫歪嘴哦的神奇术士，他是部落的中坚力量。
有一天他醒来后，发现自己居然到了联盟的主城暴风城。
在被众多联盟的士兵攻击后，他决定逃回自己的家乡奥格瑞玛。
在艾泽拉斯，有
城市之间有
每次经过一个城市，都会被收取一定的过路费（包括起点和终点），路上并没有收费站。
假设
歪嘴哦不希望花很多钱，他想知道，在可以到达奥格瑞玛的情况下，他所经过的所有城市中最多的一次收取的费用的最小值是多少。
第一行三个正整数
接下来有
再接下来有
仅一个整数，表示歪嘴哦交费最多的一次的最小值。
如果他无法到达奥格瑞玛，输出 AFK。
对于
对于
不保证不存在重边或自环。
by SSerxhs @ 2021-01-20 21:04:03
滋滋
建议公路条数换个变量，避免重复
by hhoppitree @ 2021-01-20 21:08:24
可是好像不让修改原题面啊/kk
by FunnyCreatress @ 2021-01-20 21:13:13
b 条公路
打错了罢
by hhoppitree @ 2021-01-20 21:13:53
笔误笔误
by hhoppitree @ 2021-01-20 21:14:38
fixed
by hhoppitree @ 2021-01-20 21:15:22
感谢 @FunnyCreatress /ch