topcoder srmライブコーディングでやったやつ

Div1Easyですね、なんか…

XorTravelingSalesman

幅優先のDPだとはすぐにわかって実装したんですが、uncaught exception出しまくって（よくわからないけど）本質的じゃないところを調整しまくってました。
最終的にはなんか101/100でWAとかあきらかにバグってるだろみたいなテスト結果が出てきたりしましたが、なんとかACコードに調節できた…

これは実装力の問題なのか、単なる運なのか…うーん…

class XorTravelingSalesman {
public:
  int dp[55][5555];
  int maxProfit( vector <int> cityValues, vector <string> roads ) {
    // 現在の価値 : p
    // 街の価値 : x
    // 次の価値 : p ^ x
    // 街はなんどでも通って良い、行ける価値と街、DP？
    // i-th element j-th character -> iからj
    vector<int> road[50];
    int c = cityValues.size();
    for (int i=0; i<c; i++) {
      for (int j=0; j<c; j++) {
        if (roads[i][j]=='Y') road[i].push_back(j);
      }
    }
    memset(dp, 0, sizeof(dp));
    int res = 0;
    queue<P> que;
    que.push(P(0,cityValues[0]));
    dp[0][cityValues[0]] = 1;
    while (!que.empty()) {
      P p = que.front(); que.pop();
      int npos = p.first;
      int val = p.second;
      for (int i=0; i<road[npos].size(); i++) {
        int j = road[npos][i];
        int nval = val ^ cityValues[j];
        if (dp[j][nval]) continue;
        dp[j][nval] = 1;
        que.push(P(j,nval));
      }
    }
    for (int i=0; i<c; i++) {
      for (int j=0; j<3333; j++) {
        if (dp[i][j]) res = max(res, j);
      }
    }
    return res;
  }
};