[2010国家集训队]阳阳做任务
时间限制:15s 空间限制:259MB
题目描述
阳阳是一个任务狂人,他最喜欢看到游戏的任务列表中,“可以开始”一栏为空。这天他又发现了一款新游戏…… 这个游戏由n个城市构成,用1到n的整数编号。其中城市v有fv个任务需要全部完成。但是,每次到达一个城市必须且只能完成一个任务。如果一个城市没有可以做的任务,阳阳就不能到达这个城市。做完任务以后,必须通过通道或者传送卷轴到达另外一个城市。 通道总共有m条,它们单向连接两个城市。通道 表示从城市u到城市v的通道。奇怪的是,通道 只允许玩家至多通过 次。更奇怪的是,对于任意的通道 和通道 ,若 ,则 。 传送卷轴可以从任意一个城市到达任意一个城市。特别地,可以回到原来的城市,算又到达这个城市一次,这时可以且必须再做一个任务。另外,最初你需要使用一个卷轴到达任意一个城市,最终可以停留在任意一个城市。 阳阳想知道,完成所有的任务最少需要使用多少次转送卷轴。
输入格式
第一行包含两个正整数n、m,意义见题目描述。 第二行包含n个正整数,第i个数表示fi。 接下来有m行,每行有三个正整数u、v、w,表示通道 的最多使用次数为w。
输出格式
输出一行一个整数,表示做完所有的任务所需要的最少卷轴数目。
样例输入
4 3 5 5 5 5 1 2 1 3 2 1 3 4 6
样例输出
14 【样例说明】 “—”表示通过通道到达,“…”表示通过传送卷轴到达。 一个可行的方案如下 …1—2…3—2…3—4…1…1…1…1…2…2…2…3—4…3—4…3—4…4 【数据规模及约定】 对于100%的数据,0< N < = 10^6 ,0 < M < = 10^7 , 0< W(u,v),Fv<= 10^9<="" pre="">提示
没有写明提示
题目来源
By 陈许旻
=>