SRM556Div2

Medium:
グラフと、各頂点の値が渡されるので、スタート地点からグラフを移動し、値をXORしていった時に得られる最大値を求める問題。
同じノードを複数回訪れる事も可能。

無向グラフなら
a->b->c->b->a という風に来た道を戻れば任意の値を使えるので、到達できる頂点の値をXORしたときの最大値だと思って解いた。

#include <cstdlib>
#include <cmath>
#include <map>
#include <utility>
#include <set>
#include <iostream>
#include <string>
#include <vector>
#include <algorithm>
#include <sstream>
#include <complex>
#include <stack>
#include <queue>
#define REP(i,a,b) for(int i=(a);i<(b);++i)
#define rep(i,n)  REP(i,0,n)
using namespace std;

class XorTravelingSalesman {
public:
  int maxProfit(vector <int> cityValues, vector <string> roads) {
    int result=0;

	set<int> enableValues;
	
	queue<int> q;
	q.push(0);
	enableValues.insert(cityValues[0]);
	while(!q.empty())
	{
		int n=q.front();q.pop();
		rep(i,roads.size())
		{
			if( roads[n][i]=='Y' )
			{
				enableValues.insert(cityValues[i]);
				q.push( i );
				roads[n][i]='N';
			}
		}
	}

	q.push(0);
	set<int> visited;
	visited.insert(0);
	while( !q.empty() )
	{
		int n = q.front();q.pop();
		for( set<int>::iterator it = enableValues.begin(); it!=enableValues.end(); ++it )
		{
			if( visited.find(n^(*it)) == visited.end() )
			{
				visited.insert(n^(*it));
				q.push( n^(*it));
				result = max( result , n^(*it));
			}
		}
	}
    return result;
  }