BZPRO

#2607. [Poi2003]Smugglers

内存限制：128 MiB 时间限制：3 Sec
提交 提交记录 讨论

题目描述

Byteotia 因为它丰富的金矿资源而闻名世界. 所以在和它的邻国Bitland的边界上每年都有大量的金矿交易。不幸的是由于税务的繁重，商人带着矿产穿过边境时都要交纳矿产价格的50% 作为关税。但是幸运的是，有一些炼金术士已经发明了一些方法能把某一种矿产转化成另一种。于是这样在交易时就可以先把昂贵的矿产转化成便宜的，等到带过边境以后在转换回来。但是由于这项工作费时费力，炼金术士对于每种转换都要收取相应的费用。现在有个商人想将1kg金子带过边境，他想知道最少的花费是多少。

输入格式

第一行仅一个数n表示有多少种金属矿产。1 <= n <= 5000. 接下来n行表示每种金属1kg的单价。第k +1行的数pk为第k种金属的单价。0 <= pk <= 109. 我们假设金子的标号为1。接下来一个正数m表示一共有m种转换方式。0 <= m <= 100000. 接下来m行每行描述一个转换，它由三个数a, b, c 表示把1kg的a金属转换为1kg的b金属需要c的代价。1 <= a,b <= n, 0 <= c <= 10000. 对于特定的金属对a和 b 最多只会出现一次。

输出格式

输出一行，表示把1kg的金子带过边境的最小花费。

样例

样例输入


			
4





200

100

40

2

6

1 2 10

1 3 5

2 1 25

3 2 10

3 4 5

4 1 50

样例输出


			
60

数据范围与提示

BZPRO Powered by Remmina.
Github Repository