この問題はワーシャルフロイド法 (Floyd-Warshall algorithm) と呼ばれるアルゴリズムを実装すれば解くことが出来ます。

この問題をグラフの問題に言い換えると次のようになります。

• 頂点 \(1_0, 2_0, \dots, N_0, 1_1, 2_1, \dots, N_1\) がある。\(v_0\) は割引券を使わずに頂点 \(v\) にいる状態、\(v_1\) は割引券を使って頂点 \(v\) にいる状態に対応している。
• \(u_0, v_0\) 間と \(u_1, v_1\) 間には重み \(a_{u, v}\) の辺が双方向に張られている。また、\(u_0, v_1\) 間と \(v_0, u_1\) 間には重み \(b_{u,v}\) の辺が一方向に張られている。
• このとき、\(u_0\) から \(v_1\) へ向かう最短経路の距離が \(c_{u,v}\) 、すなわち求めたい答えとなる。

言い換えると、この問題は \(2N\) 頂点間の全点対最短経路を計算する問題と言えます。全点対最短経路問題はワーシャルフロイド法を利用すれば \(\mathrm{O}(N^3)\) で計算できることが知られているので、ワーシャルフロイド法をを実装すればこの問題を解くことが出来ます。 計算量は \(\mathrm{O}(N^3)\) で十分高速です。

• 実装例(C++)

#include <iostream>
using namespace std;

#define rep(i, n) for (int i = 0; i < (int)(n); i++)

int A[333][333], B[333][333], dp[333][333][2];

int main() {
  int N;
  cin >> N;
  rep(i, N) {
    for (int j = i + 1; j < N; j++) {
      cin >> A[i][j];
      A[j][i] = A[i][j];
    }
  }
  rep(i, N) {
    for (int j = i + 1; j < N; j++) {
      cin >> B[i][j];
      B[j][i] = B[i][j];
    }
  }
  rep(i, N) rep(j, N) {
    dp[i][j][0] = A[i][j];
    dp[i][j][1] = B[i][j];
  }
  auto chmin = [&](int& s, int t) { s = min(s, t); };
  rep(k, N) rep(i, N) rep(j, N) {
    chmin(dp[i][j][0], dp[i][k][0] + dp[k][j][0]);
    chmin(dp[i][j][1], dp[i][k][0] + dp[k][j][1]);
    chmin(dp[i][j][1], dp[i][k][1] + dp[k][j][0]);
  }
  rep(i, N) {
    for (int j = i + 1; j < N; j++) {
      cout << dp[i][j][1] << " \n"[j == N - 1];
    }
  }
}