Hatena::Grouptopcoder

cafelier@SRM

cafelier のSRM参加記録です。コンテスト中に考えてたことを執拗に全部書き残すとどうなるだろうかという試み本番中にこういうコードが書きたかったなあ、という後で書いた反省コードを書き残す試み

スパムが来たのでしばらくコメント欄をはてなユーザ限定にしています、すみません、

 | 

2010-02-14

SRM461 500

| 12:30 | はてなブックマーク -  SRM461 500 - cafelier@SRM

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だったのがイマイチ美しくないので、もっと自然に探索を打ち切れる条件があるような気がするんだけども。

トラックバック - http://topcoder.g.hatena.ne.jp/cafelier/20100214
 | 

presented by cafelier/k.inaba under CC0