#codefestival2016qualBc. [codefestival_2016_qualB_c]Gr-idian MST

[codefestival_2016_qualB_c]Gr-idian MST

H×WH \times W 的二维平面,0iH,0jW\forall 0\le i\le H, 0\le j\le W 有一个点。连接 (i,j)(i, j)(i+1,j)(i + 1, j) 的边权为 pip_i0jW0\le j\le W),连接 (i,j)(i, j)(i,j+1)(i, j + 1) 的边权为 qjq_j。求这张 (H+1)×(W+1)(H + 1)\times (W + 1) 个点的图的最小生成树的边权和。1H,W1051\le H, W\le 10^51pi,qj1081\le p_i,q_j\le 10^8

Translated by @YangTY