BZPRO

#5377. [2018国家队集训队互测]有向图

内存限制：512 MiB 时间限制：300 Sec
提交 提交记录 讨论

题目描述

给定一个n个点m条边的有向弱连通图，每个点均匀点权di和修改耗时wi，每次修改可以花费wi的时间把di
加1或者减1，求最少消耗多少时间，使得∀(u,v)∈E,du≤dv。

输入格式

输入共包括m+3行
第一行包含两个整数n,m表示点数和边数。
第二行包含n个整数，第i个整数表示第i个点的点权di。
第三行包含n个整数，第i个整数表示第i个点的修改耗时wi。
第4m+3行，每行包含两个整数ui,vi表示有向图种的一条由ui到vi的有向边。
n<=300000,m=n或m=n-1

输出格式

输出包含一个整数，表示最小总耗时。

样例

样例输入


			
3 3

5 9 8

1 2 3

1 2

2 3

3 1

样例输出


			
5



样例解释 1

限制为 d1<=d2, d2<=d3,d3<=d1，即要求d1=d2=d3，故将d1加3至8，d2减1至8最优，最下耗时为1*|5-8|+2*|9-8|+3*|8-8|=5

数据范围与提示

BZPRO Powered by Remmina.
Github Repository