SRM556 Div1 Easy(250), Div2 Medium(500) XorTravelingSalesman
XorTravelingSalesman
拡張ダイクストラ。(街,利益)を1個のノードと見なす。
街Xに到達できるならば、0→a→b→X→b→a→0と同じ経路を往復することで、街Xの点数だけを得られるので……という解き方もあるとチャットで聞いた。
#include <string> #include <vector> #include <queue> using namespace std; class XorTravelingSalesman{public: int maxProfit( vector <int> cityValues, vector <string> roads ) { int N = (int)cityValues.size(); vector<vector<bool> > F(N,vector<bool>(1024,false)); F[0][cityValues[0]] = true; queue<int> Q; Q.push(cityValues[0]); int ans = cityValues[0]; while ( !Q.empty() ) { int c = Q.front()/1024; int p = Q.front()%1024; Q.pop(); ans = max(ans,p); for ( int i=0; i<N; i++ ) if ( roads[c][i]=='Y' ) { int t = p^cityValues[i]; if ( !F[i][t] ) { F[i][t] = true; Q.push(i*1024+t); } } } return ans; }};