SRM525 Div1 Medium

525
もし、ある時点で知っている噂が1種類だけなら、それを伝えた方が日数がかからないのは明白。
ただ、1日に伝播されられる噂は1つだけ。
同時に2つの噂を知ったときに、どうすれば最適なのかは簡単には分からなそう。
しかし、２つの噂のどちらを先に伝えるかは2^N通りしかないので、全パターン試せる。

class Rumor {
public:
  int getMinimum(string K, vector <string> graph)
  {
    const int inf = 1 << 28;
    const int N = K.size();
    int g[N][N];
    for (int i = 0; i < N; ++i) {
      for (int j = 0; j < N; ++j) {
        g[i][j] = (graph[i][j] == 'Y') ? 1 : inf;
      }
      g[i][i] = 0;
    }

    REP (k, N) REP (i, N) REP (j, N) {
      g[i][j] = min(g[i][j], g[i][k] + g[k][j]);
    }

    int d[N];
    fill(d, d + N, inf);
    for (int i = 0; i < N; ++i) {
      if (K[i] == 'Y') {
        for (int j = 0; j < N; ++j) {
          d[j] = min(d[j], g[i][j]);
        }
      }
    }

    vector<int> v[N];
    for (int i = 0; i < N; ++i) {
      if (d[i] == inf) return -1;
      v[d[i]].push_back(i);
    }

    int mn = inf;
    int rumor[N][2];
    for (int bit = 0; bit < (1 << N); ++bit) {
      fill(&rumor[0][0], &rumor[N-1][2], inf);
      for (int i = 0; i < N; ++i) {
        if (K[i] == 'Y') rumor[i][0] = rumor[i][1] = 0;
      }

      for (int i = 0; i+1 < N; ++i) {
        for (int j = 0; j < v[i].size(); ++j) {
          int a = rumor[v[i][j]][0];
          int b = rumor[v[i][j]][1];
          if (a == b) {
            if (0 == (bool)(bit & (1 << v[i][j]))) ++a;
            else ++b;
          }
          for (int k = 0; k < v[i+1].size(); ++k) {
            if (g[v[i][j]][v[i+1][k]] == 1) {
              int &n = rumor[v[i+1][k]][0];
              n = min(n, a + 1);
              int &m = rumor[v[i+1][k]][1];
              m = min(m, b + 1);
            }
          }
        }
      }
      mn = min(mn, *max_element(&rumor[0][0], &rumor[N-1][2]));
    }

    return mn < inf ? mn : -1;
  }

};