#2470. 「2018 集训队互测 Day 2」有向图

内存限制:512 MiB 时间限制:3000 ms 标准输入输出
题目类型:传统 评测方式:文本比较
上传者: samzhang

题目描述

给定一个 n 个点 m 条边的有向弱连通图, 每个点均匀点权 d_i 和修改耗时 w_i , 每次修改可以花费 w_i 的时间把 d_i 1 或者减 1 ,求最少消耗多少时间,使得 \forall (u,v)\in E, d_u\le d_v

输入格式

输入共包括 m+3
第一行包含两个整数 n,m ,表示点数和边数。
第二行包含 n 个整数,第 i 个整数表示第 i 个点的点权 d_i
第三行包含 n 个整数,第 i 个整数表示第 i 个点的修改耗时 w_i
4 ~ m+3 行,每行包含两个整数 u_i,v_i ,表示有向图种的一条由 u_i v_i 的有向边。

输出格式

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

样例

样例输入1

3 3
5 9 8
1 2 3
1 2
2 3
3 1

样例输出 1

5

样例解释 1

限制为 d_1\le d_2,d_2\le d_3,d_3\le d_1 ,即要求 d_1 = d_2 = d_3 ,故将 d_1 3 8 d_2 1 8 最优,最小耗时为 1 \times |5-8| + 2\times |9-8| + 3 \times |8-8| = 5

样例输入2

3 2
5 9 8
1 2 3
1 2
2 3

样例输出 2

2

数据范围与提示

子任务 分值 n \leq m= 特殊限制
1 10 5000 n-1
2 20 100000 将所有有向边看成无向边时,整张图构成一条链
3
4 15 300000
5 10 n 存在数列 f_i ,满足有且仅有 i f_i 的有向边, w_i=1
6 将所有有向边看成无向边时,整张图构成一个环
7 15 n-1,n