Skip to content

11415: 【原1415】Flover_06

题目

题目描述

author: Flover 原OJ链接:https://acm.sjtu.edu.cn/OnlineJudge-old/problem/1415

Time Limit

1s

Description

有一天,Flover 要去找膜拜 Taring。到了 Taring 家附近才发现,想要膜拜 Taring 并不是一件容易的事。

Taring 家的大门外有n个站台,用 \(1\) 到 \(n\) 的正整数编号,Flover 需要对每个站台访问恰好一定次数以后才能膜拜 Taring。站台之间有 \(m\) 个单向的传送门,通过传送门到达另一个站台不需要花费任何代价。而如果不通过传送门,Flover 就需要乘坐公共汽车,并花费 \(1\) 单位的钱。值得庆幸的是,任意两个站台之间都有公共汽车直达。

现在给订每个站台必须访问的次数,对于站台 \(i\),Flover 必须恰好访问 \(F_i\) 次(不能超过)。

我们用 \(u, v, w\) 三个参数描述一个传送门,表示从站台 \(u\) 到站台 \(v\) 有一个最多可以使用 \(w\) 次的传送门(不一定要使用 \(w\) 次)。对于任意一对传送门 \( (u_1, v_1) \) 和 \( (u_2, v_2) \),如果有 \( u_1 < u_2\),则有 \(v_1 \leqslant v_2\);如果有 \( v_1 < v_2\),则有 \(u_1 \leqslant u_2\);且 \(u_1 = u_2\) 和 \(v_1 = v_2\) 不同时成立。

Flover 可以从任意的站台开始,从任意的站台结束。出发去开始的站台需要花费 \(1\) 单位的钱。Flover 需要求出打开大门最少需要花费多少单位的钱,但是 Flover 实在是太笨了,所以特来向你求救!^_^。

Input Format

第一行包含两个正整数 \(n, m\),意义见题目描述。

第二行包含 \(n\) 个正整数,第 \(i\) 个数表示 \(F_i\)。

接下来有 \(m\) 行,每行有三个正整数 \(u, v, w\),表示从 \(u\) 到 \(v\) 有一个可以使用 \(w\) 次的传送门。

Output Format

输出一行一个整数,表示 Flover 为了膜拜 Taring 最少花费。

Sample Input I

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

Sample Output I

17

Data Range

有20%的数据满足 \( n \leqslant 10, m \leqslant 50\);

有50%的数据满足 \( n \leqslant 1000,m \leqslant 10000\) 。

100%的数据满足 \( 1 \leqslant n \leqslant 10000,1 \leqslant m \leqslant 100000\);

对于所有的 \(u, v\) ,满足 \(1 \leqslant u, v \leqslant n, u \neq v \);对于所有的 \(w, F_i\),满足 \( 1 \leqslant w, F_i \leqslant 50000\)。

对于所有的 \(w, F_i\) ,满足 \( 1 \leqslant w, F_i \leqslant 10\) ;

以上的每类数据中都存在50%的数据满足对于所有的 \(w, F_i\),有 \(w=F_i=1\)。

Oops! 本题目还没有解答!

助教老师们编题的速度,已经超过了解题的速度!

OJ翻了一新,但本解答集还大多用的是2017-2019级,甚至更早的同学们贡献的答案。

如果你已经AC了,可以的话,请您参考添加页面,与大家一起分享你的题解!