4477: 「2018 集训队互测 Day 2」有向图
内存限制：512 MB
时间限制：3.000 S
评测方式：文本比较
命题人：
提交：0
解决：0
题目描述
给定一个 $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$ 的有向边。
输出
输出包含一个整数，表示最小总耗时。
样例输入 复制
3 3
5 9 8
1 2 3
1 2
2 3
3 1样例输出 复制
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$ | $n-1$ | 将所有有向边看成无向边时，整张图构成一条链 | | $3$ | $20 $ | $100000$ | $n-1$ | 无 | | $4$ | $15$ | $300000$ | $n-1$ | 无 | | $5$ | $10$ | $300000$ | $n$ | 存在数列$f_i$,满足有且仅有$i$向$f_i$的有向边，$w_i=1$ | | $6$ | $10 $ | $300000$ | $n$ | 将所有有向边看成无向边时，整张图构成一个环 | | $7$ | $15$ | $300000$ | $n-1,n$ | 无 |