頂点数 \(N+1\) のグラフを考える. 頂点 \(1\) から \(N\) が各商品に対応している.
頂点 \(N+1\) から頂点 \(i\) に重み \(C_i\) の辺をつなぐ. これが手数料に対応する. そして, 頂点 \(i-1\) から頂点 \(i\) に重み \(D_i\) の辺をつなぐ. これが梱包料に対応する. このグラフの最小全域木を求めれば必要な手数料と梱包料が分かる. あとはすべての商品の価格を合計したものを足せば最小の費用が求められる.
最小全域木はクラシカル法を使えばいい.