[NOIP 2009 提高组] 最优贸易

题目描述

有 $n$ 座城市和 $m$ 条道路，任意两座城市之间最多一条道路。道路可能是单向或双向的。城市 $i$ 的水晶球买入价和卖出价均为 $a_i$。商人从城市 $1$ 出发，最终到达城市 $n$，途中可以重复经过城市。他可以进行至多一次交易：先在一个经过的城市买入一个水晶球，再在之后经过的城市卖出。也可以完全不交易。求最大利润。

输入格式

第一行输入 $n,m$。第二行输入 $n$ 个整数，依次表示各城市价格。接下来 $m$ 行，每行输入 $x,y,z$。$z=1$ 表示从 $x$ 到 $y$ 的单向道路，$z=2$ 表示两者之间的双向道路。

输出格式

输出最大利润。如果不交易最优，输出 $0$。

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

5

说明与数据范围

保证城市 $1$ 可以到达城市 $n$。$1\le n\le100000$，$1\le m\le500000$，$1\le a_i\le100$，$1\le x,y\le n$，$1\le z\le2$。原题中，10% 的数据 $n\le6$，30% 的数据 $n\le100$，50% 的数据为无环图。本题包重新生成数据，每点等分，不沿用原题子任务比例。样例可走 $1\to4\to5\to4\to5$，在第一次到达 $5$ 时以 $1$ 买入、随后在 $4$ 以 $6$ 卖出，利润为 $5$。

来源

P1073