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; 
}};