cafelier@SRM

SRM461 500

あとで | 12:30 |

Dijkstraで。

class BuildingCities { public:
   int findMinimumCities(int maxDirect, int maxTravel, vector <int> cityX, vector <int> cityY) 
   {
      int result = 0x7fffffff;

      const int N = cityX.size();
      typedef pair<int,    int>  vert; // city, extra_city_built
      typedef pair<double, vert> cedge;

      // dijkstra
      set<vert> V;
      priority_queue< cedge, vector<cedge>, greater<cedge> > Q;
      Q.push( cedge(0, vert(0,0)) );
      while( !Q.empty() )
      {
         // pop
         double d = Q.top().first;
         vert   v = Q.top().second;
         int   vc = v.first;
         int   vs = v.second;
         Q.pop();
         if( V.count(v) )
            continue;
         V.insert(v);

         // goal
         if( vc==N-1 )
            result = min(result, vs);

         // next
         for(int j=0; j<N; ++j) if( vc != j )
         {
            double dd = hypot( cityX[vc] -cityX[j], cityY[vc] -cityY[j] );
            double dx = hypot( cityX[N-1]-cityX[j], cityY[N-1]-cityY[j] );
            vert u(j, vs+int(dd/maxDirect - 1e-10));
            if( d+dd+dx<=maxTravel && u.second<result && !V.count(u) )
               Q.push( cedge(d+dd, u) );
         }
      }
      return result==0x7fffffff ? -1 : result;
   }
};

これ想定解なのかな。変な枝刈り入れないとTLEだったのがイマイチ美しくないので、もっと自然に探索を打ち切れる条件があるような気がするんだけども。