TCO17 Algorithm Round 2A DistanceZeroAndOne

以下備忘録
解法：
d0,d1からグラフを構築し、それらのグラフを１つにまとめる
ある辺を答えとなるグラフに追加するかどうかは次のように決定する
1. d0,d1から構築したグラフの両方がその辺を持つなら答えのグラフにもその辺を追加
2. 片方しか持たないなら、その辺を追加した場合もう片方の最短距離に影響しないかどうかをチェックし、影響しないなら追加
最後にこうしてできたグラフの0,1からの最短距離がd0,d1と一致するか調べる

コード：

#include<bits/stdc++.h>

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

using namespace std;

typedef long long ll;
const int IINF = INT_MAX;

class DistanceZeroAndOne {
public:
  
  vector<int> bfs(vector<string> &G,int sp) {
    int n = G.size();
    vector<int> mini(n,IINF);
    mini[sp] = 0;
    deque<int> deq;
    deq.push_back(sp);
    while( !deq.empty() ) {
      int c = deq.front(); deq.pop_front();
      rep(i,n) {
        if( G[c][i] == 'Y' )  {
          if( mini[c] + 1 < mini[i] ) {
            mini[i] = mini[c] + 1;
            deq.push_back(i);
          }
        }
      }
    }
    return mini;
  }

  bool check(vector<string> &G,vector<int> &d0,vector<int> &d1) {
    vector<int> m0 = bfs(G,0);
    vector<int> m1 = bfs(G,1);
    if( m0 == d0 && m1 == d1 ) return true;
    return false;
  }

  void makeG(vector<string> &G,vector<int> &d,int sp) {
    int n = G.size();
    vector<int> pre;
    pre.push_back(sp);
    REP(i,1,n) {
      vector<int> nex;
      rep(j,n) if( d[j] == i ) {
        nex.push_back(j);
        rep(k,(int)pre.size()) {
          G[j][pre[k]] = 'Y';
          G[pre[k]][j] = 'Y';
        }
      }
      pre = nex;
    }
  }

  vector <string> construct( vector <int> d0, vector <int> d1 ) {
    int n = d0.size();
    vector<string> ans(n);
    vector<string> G0(n),G1(n);
    rep(i,n) ans[i] = G0[i] = G1[i] = string(n,'N');
    makeG(G0,d0,0);
    makeG(G1,d1,1);
    rep(i,n) {
      rep(j,n) {
        if( G0[i][j] != G1[i][j] ) {
          char tmp = 'N';
          if( G0[i][j] == 'Y' ) {
            int vi = d1[i], vj = d1[j];
            if( vi + 1 < vj || vj + 1 < vi )  tmp = 'N';
            else tmp = 'Y';
          } else {
            int vi = d0[i], vj = d0[j];
            if( vi + 1 < vj || vj + 1 < vi )  tmp = 'N';
            else tmp = 'Y';
          }
          ans[i][j] = tmp;
        } else {
          ans[i][j] = G0[i][j];
        }
      }
    }
    if( check(ans,d0,d1) ) return ans;
    return vector<string>();
  }
};