AT_abc188_e [ABC188E] Peddler

题目描述

高桥国有 $N$ 个城镇，编号从 $1$ 到 $N$。
此外，这个国家有 $M$ 条道路。通过第 $i$ 条道路，可以从城镇 $X_i$ 前往城镇 $Y_i$。不能逆向通行。保证 $X_i < Y_i$。
在这个国家，黄金交易非常活跃。在第 $i$ 个城镇，可以以 $A_i$ 日元的价格买入或卖出 $1\,\mathrm{kg}$ 黄金。

作为旅行商人的高桥君，计划在高桥国内的某个城镇买入 $1\,\mathrm{kg}$ 黄金，经过若干条道路后，在与买入城镇不同的另一个城镇卖出 $1\,\mathrm{kg}$ 黄金。
此时，请求出高桥君能够获得的最大利润（即 $($卖出黄金的价格$) - ($买入黄金的价格$)$）。

输入格式

输入以以下格式从标准输入读入。

$N$ $M$
$A_1$ $A_2$ $A_3$ $\dots$ $A_N$
$X_1$ $Y_1$
$X_2$ $Y_2$
$X_3$ $Y_3$
$\vdots$
$X_M$ $Y_M$

输出格式

输出答案。

输入输出样例 #1

输入 #1

4 3
2 3 1 5
2 4
1 2
1 3

输出 #1

3

输入输出样例 #2

输入 #2

5 5
13 8 3 15 18
2 4
1 2
4 5
2 3
1 3

输出 #2

10

输入输出样例 #3

输入 #3

3 1
1 100 1
2 3

输出 #3

-99

说明/提示

限制条件

• $2 \le N \le 2 \times 10^5$
• $1 \le M \le 2 \times 10^5$
• $1 \le A_i \le 10^9$
• $1 \le X_i < Y_i \le N$
• $(X_i, Y_i) \neq (X_j, Y_j)\ (i \neq j)$
• 输入中的所有值均为整数

样例解释 1

可以通过如下方式获得 $3$ 日元的利润：

• 在城镇 $1$ 以 $2$ 日元买入 $1\,\mathrm{kg}$ 黄金
• 通过道路 $2$ 前往城镇 $2$
• 通过道路 $1$ 前往城镇 $4$
• 在城镇 $4$ 以 $5$ 日元卖出 $1\,\mathrm{kg}$ 黄金

样例解释 2

可以通过如下方式获得 $10$ 日元的利润：

• 在城镇 $2$ 以 $8$ 日元买入 $1\,\mathrm{kg}$ 黄金
• 通过道路 $1$ 前往城镇 $4$
• 通过道路 $3$ 前往城镇 $5$
• 在城镇 $5$ 以 $18$ 日元卖出 $1\,\mathrm{kg}$ 黄金

样例解释 3

请注意，由于不能在买入黄金的城镇卖出黄金，答案可能为负数。

由 ChatGPT 4.1 翻译