← 返回题目

题库练习最优贸易

← 上一题下一题 →

A3435 | $最优贸易$

来源NOIP提高组 / 2009

时间限制1s

内存限制128MB

通过 / 提交0/0

题目描述

C国有n个大城市和m条道路，每条道路连接这n个城市中的某两个城市。任意两个城市之间最多只有一条道路直接相连。这m条道路中有一部分为单向通行的道路，一部分为双向通行的道路，双向通行的道路在统计条数时也计为1条。 C国幅员辽阔，各地的资源分布情况各不相同，这就导致了同一种商品在不同城市的价格不一定相同。但是，同一种商品在同一个城市的买入价和卖出价始终是相同的。 商人阿龙来到C国旅游。当他得知同一种商品在不同城市的价格可能会不同这一信息之后，便决定在旅游的同时，利用商品在不同城市中的差价赚回一点旅费

输入格式

每组输入数据的第一行包含2个正整数n和m，中间用一个空格隔开，分别表示城市的数目和道路的数目。 第二行n个正整数，每两个正整数之间用一个空格隔开，按标号顺序分别表示这n个城市的商品价格。 接下来m行，每行有3个正整数，x，y，z，每两个整数之间用一个空格隔开。如果z=1，表示这条道路是城市x到城市y之间的单向道路；如果z=2，表示这条道路为城市x和城市y之间的双向道路。 数据规模： 输入数据保证1号城市可以到达n号城市。 对于10%的数据，1\leqn\leq6。 对于30

输出格式

每组输出共1行，包含1个整数，表示最多能赚取的旅费。如果没有进行贸易，则输出0。

输入输出样例

输入 #1

输出 #1

C++ 编辑器

输入

输出