给定一个 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
限制为 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 。
3 2 5 9 8 1 2 3 1 2 2 3
2