読者です 読者をやめる 読者になる 読者になる

SRM 661 Div2 Medium BridgeBuildingDiv2

問題

ノードが2列に並んでいて,各列はN個のノードが一直線に並んでいる. 一直線に並んだN個のノードのi番目のノードとi+1番目のノードは間隔がa[i]b[i]の枝で接続されている. (aは一列目,bは二列目に対応). 今,一列目と二列目の同じインデックスのノードを間隔0のK本の枝を張る時, 任意のノードの最短経路の最大を求める問題.

解答

  • 各列のノード数が高々11と小さいので,K本の枝の張り方を全て考え,全てのノード間の最短路の計算
  • 各枝の張り方で最短経路の最大を求め,出力する.
class BridgeBuildingDiv2
{
public:
  int minDiameter(vector <int> a, vector <int> b, int K)
    {
      int N = a.size()+1;
      int n = 2*N;
      long long inf = 100 * n;
      vector<vector<long long> > dis(n, vector<long long>(n, inf));
      for(int i = 0; i < N-1; i++){
        dis[i][i+1] = a[i];
        dis[i+1][i] = a[i];
        dis[i+N][i+1+N] = b[i];
        dis[i+1+N][i+N] = b[i];
      }
      for(int i =  0; i < N; i++) dis[i][i] = 0;
      vector<bool> connected = vector<bool>(N, false);
      for(int i = 0; i < K; i++) connected[N-i-1] = true;
      long long res = inf;
      do{
        // cout << "res=" << res << endl;
        vector<vector<long long> > min_dis = dis;
        for(int i = 0; i < N; i++){
          if (connected[i]){
            min_dis[i][N+i] = 0;
            min_dis[N+i][i] = 0;
          }
        }
        for(int k = 0; k < n;k++){
        for (int i = 0; i < n; i++){
          for(int j = 0; j < n; j++){
              if (min_dis[i][k] + min_dis[k][j] < min_dis[i][j]){
                min_dis[i][j] = min_dis[i][k] + min_dis[k][j];
              }
            }
          }
        }
        long long m = 0;
        for(int i = 0; i < n; i++){
          for(int j = i+1; j < n; j++){
            m = max(m, min_dis[i][j]);
            // cout << "i=" << i << " j=" << j << " dis=" << min_dis[i][j] << endl;
          }
        }
        res = min(res, m);
     }while(next_permutation(connected.begin(), connected.end()));
      return res;
    }
};