P14485 [集训队互测 2018] 有向图

试题来源：，向 LOJ 和出题人表示感谢。如果版权方并不希望试题出现在洛谷，可联系洛谷管理组撤下试题。

给定一个 $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$ 的有向边。

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

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