cafelier@SRM

SRM492 550

あとで | 13:14 |

• 50⁵/6 のオーダだけどまあ無理矢理

static const LL INF = 0x1fffffffffffffffLL;

template<typename T>
struct DP3
{
   int N1, N2, N3;
   vector<T> data;
   DP3(int N1, int N2, int N3, const T& t = T())
      : N1(N1), N2(N2), N3(N3), data(N1*N2*N3, t) { assert(data.size()*sizeof(T)<(1<<26)); }
   T& operator()(int i1, int i2, int i3)
      { return data[ ((i1*N2)+i2)*N3+i3 ]; }
   void swap(DP3& rhs)
      { data.swap(rhs.data); }
};

class TimeTravellingTour { public:
   long long determineCost(int N, vector <int> cities, vector <string> roads) 
   {
      vector< vector<LL> > G(N, vector<LL>(N,INF));
      {
         string str = accumulate(roads.begin(), roads.end(), string(""));
         for(int i=0; i<str.size(); ++i)
            if( str[i] == ',' )
               str[i] = ' ';
         stringstream sin(str);
         for(int a,b,cost; sin>>a>>b>>cost; )
            G[a][b] = G[b][a] = cost;
      }
      for(int i=0; i<N; ++i)
         G[i][i] = 0;
      for(int k=0; k<N; ++k)
         for(int i=0; i<N; ++i)
            for(int j=0; j<N; ++j)
               G[i][j] = min(G[i][j], G[i][k]+G[k][j]);

      DP3<LL> memo(N, cities.size()+1, cities.size()+1, -1);
      LL a = rec( 0, 0, cities.size(), cities, G, memo );
      return a>=INF ? -1 : a;
   }

   LL rec(int cur, int s, int e, const vector<int>& C, const vector< vector<LL> >& G, DP3<LL>& memo )
   {
      if( s+1 == e )
         return G[cur][C[s]];
      if( memo(cur,s,e) >= 0 )
         return memo(cur,s,e);

      LL best = INF;
      for(int v=0; v<G[cur].size(); ++v)
         if( G[cur][v] < INF )
            for(int m=s+1; m<e; ++m)
               best = min(best, G[cur][v]+rec(v,s,m,C,G,memo)+rec(v,m,e,C,G,memo));
      return memo(cur,s,e) = best;
   }
};