PID731 / 混乱的入口
题目描述

你去找路人甲玩,到了门口才发现一件有点小坑爹的事情

因为找到他家的入口不是一件容易的事……

他们家很穷,但是他有个好GF,所以他们家装饰的富丽堂皇。

路人甲府邸的门外有n个召唤师平台,以1至n的正整数命名。你必须对每个召唤师平台访问一定的次数之后才能发现入口。召唤师平台之间有m个单向的飞行阵,通过飞行阵到达另一个召唤师平台不需要花费任何代价。而如果不通过飞行阵,你就需要乘坐飞艇,并花费1单位的钱。幸运的是,你能做飞艇飞到那里,就可以从那里飞回来。

现在给你每个召唤师平台必须访问的次数Fi,对于平台i,你必须恰好访问Fi次(不能超过)。

我们用a、b、c三个参数描述一个飞行阵,表示从召唤师平台a到召唤师平台b有一个最多可以使用c次的飞行阵(不一定非要使用c次)。值得注意的是,对于任意一对飞行阵(a1,b1)和(a2,b2),如果有a1<a2,则有b1≤b2;如果有b1<b2,则有a1≤a2;且a1=a2和b1=b2不同时成立。

你可以从任意的平台开始,从任意的平台结束。出发去开始的平台需要花费1单位的钱。你需要求出找到入口最少需要花费多少单位的钱。

输入格式

第1行包含两个正整数n、m,具体意义参考题目描述。

第2行包含n个正整数,第i个数表示Fi。

接下来有m行,每行有三个正整数a、b、c,表示从a到b有一个可以使用c次的飞行阵。

输出格式

输出一行一个整数,表示找到入口花费的最少钱数。

样例输入
样例输出
注释

【数据规模及约定】

存在20%的数据满足n≤10,m≤50;对于所有的c、Fi,满足1≤c,Fi≤10。

存在50%的数据满足n≤1000,m≤10000。

对于100%的数据满足1≤n≤10000,1≤m≤100000;对于所有的a、b,满足1≤a,b≤n,a≠b;对于所有的c、Fi,满足1≤c,Fi≤50000。

以上的每类数据中都存在50%的数据满足对于所有的c、Fi,有c=Fi=1。

提交题目 Error [ 更改语言 ] Language
C C++ Pascal Python2
相关讨论
查看更多讨论
发布新讨论 讨论