\(2\) つの駅の位置をそれぞれ \((i_S, j_S)\) と \((i_T, j_T)\) とします。 一般性を失うことなく \(i_S \leq i_T\) と仮定します。
ここでは、\(j_S \leq j_T\) を満たす \(2\) 駅の建て方の中で鉄道建設の費用が最小となるものを求める方法を述べます。 つまり、ここでは \((i_S, j_S)\) の南東側に \((i_T, j_T)\) があるような建て方のみを考えます。 何故なら、\(j_S > j_T\) となる \(2\) 駅の建て方を調べるには、以下に述べる方法をグリッドの左右を反転して再度適用すれば良いからです。

\(i_S \leq i_T\) かつ \(j_S \leq j_T\) を満たす \(2\) 駅の建て方の中で費用が最小となるものを求めるために、まず鉄道建設の過程を以下のように言い換えます。

1. 青木君が好きなマスに降り立ち、そこに駅を建設する。このとき駅の建設費用が発生する。

2. 青木君が、「いまいるマスから南または東の隣接するマスへと線路を引きながら移動する」ことを \(1\) 回以上好きな回数繰り返す。ただし、グリッドの外へ出ることはできない。青木君が \(1\) 回移動するたびに線路の建設費 \(C\) 円が発生する。

3. 青木君が移動を終えた先のマスに駅を建設し、青木君はどこかへ飛び立つ。このとき駅の建設費用が発生する。

上記の方法で行う鉄道建設の方法の中で、かかる費用の合計が最小のものを求めれば良いです。
動的計画法によってこの問題を解きます。 まず \(\mathrm{dp}[i][j]\) を

\(\mathrm{dp}[i][j]\) := （青木君が一方の駅をすでに建設して、現在 \((i, j)\) にいるとき、それまでにかかった費用として考えられる最小値）

と定義します。 「青木君が一方の駅をすでに建設して、現在 \((i, j)\) にいる」ケースは、以下の \(3\) つの場合に分けられます。

• 青木君が \((i, j)\) に降り立ち、そこに駅を建てた。
• 青木君が \((i-1, j)\) から線路を引きながら \((i, j)\) に移動してきた。
• 青木君が \((i, j-1)\) から線路を引きながら \((i, j)\) に移動してきた。

上記の \(3\) つのケースに対応して、\(\mathrm{dp}[i][j]\) は次の漸化式で表せます。

\(\mathrm{dp}[i][j] = \min \lbrace A_{i, j}, \mathrm{dp}[i-1][j] + C, \mathrm{dp}[i][j-1] + C \rbrace\)

ただし、\(i = 0\) または \(j=0\) のときは \(\mathrm{dp}[i][j] := \infty\) とします。
この漸化式を用いれば、すべての \(i = 1, 2, \ldots, H, j = 1, 2, \ldots, W\) について \(\mathrm{dp}[i][j]\) を求めることが \(\mathrm{O}(HW)\) 時間でできます。

以下で、\(\mathrm{dp}[i][j]\)の値を用いて問題の答えを求める方法を述べます。 まず \(X[i][j]\) を、

\(X[i][j]\) := （ \(2\) つ目の駅を \((i, j)\) に建てて青木君がどこかへ飛び立ったとき、そこまでにかかった費用として考えられる最小値）

と定義します。
「 \(2\) つ目の駅を \((i, j)\) に建てて青木君がどこかへ飛び立った」ケースは以下の \(2\) つに分けられます。（ \(2\) つの駅は異なるマスに建てなければならないことに注意してください。）

• 青木君が \((i-1, j)\) から線路を引きながら \((i, j)\) に移動してきて、\((i, j)\) に駅を建設して飛び立った。
• 青木君が \((i, j-1)\) から線路を引きながら \((i, j)\) に移動してきて、\((i, j)\) に駅を建設して飛び立った。

上記の \(2\) つのケースに対応して、\(X[i][j]\)は次の式で求められます。

\(X[i][j] = \min \lbrace \mathrm{dp}[i-1][j] + C + A_{i, j}, \mathrm{dp}[i][j-1] + C + A_{i, j} \rbrace\)

青木君はどこかのマスから飛び立つことになるので、すべての \(i = 1, 2, \ldots, H, j = 1, 2, \ldots, W\) について \(X[i][j]\) を調べれば良いです。
すなわち、この問題の答えは \(\displaystyle\min_{1 \leq i \leq W, 1 \leq j \leq H} X[i][j]\) です。

このアルゴリズムの時間計算量は \(\mathrm{O}(HW)\) であり、この問題に正解するために十分高速です。