cafelier@SRM

SRM Member Pilot 2 450

あとで | 18:07 |

都市１個の場合への対処。あと、最初 airportCost*N から始めて、つながるたびに -=airportCost していくルーチンだと精度が足りてなかった。airportCost*その時のサイズ、を毎回計算する様に。以外といろんなとこがボロボロだな…

あと、TZTester改から空のテストケースを２個生成して、埋めないとコンパイル通らないようにして挑むようにしました。これくらいしないと僕はいつまでもコーナーケースを忘れ続ける。

struct UnionFind
{
   vector<int> uf, sz;
   int nc;

   UnionFind(int N): uf(N), sz(N,1), nc(N)
      { for(int i=0; i<N; ++i) uf[i] = i; }
   int size()
      { return nc; }
   int Find(int a)
      { return uf[a]==a ? a : uf[a]=Find(uf[a]); }
   bool Union(int a, int b)
      {
         a = Find(a);
         b = Find(b);
         if( a != b )
         {
            if( sz[a] >= sz[b] ) swap(a, b);
            uf[a] = b;
            sz[b] += sz[a];
            --nc;
         }
         return (a!=b);
      }
};

class TransportationNetwork { public:
   double minCost(vector <int> cityX, vector <int> cityY, double roadCost, double airportCost) 
   {
      const int N = cityX.size();
      if( N == 1 )
         return 0.0;

      typedef pair<int,int>     edge;
      typedef pair<double,edge> cedge;

      priority_queue< cedge, vector<cedge>, greater<cedge> > Q;
      for(int i=0; i<N; ++i)
         for(int j=i+1; j<N; ++j)
         {
            double L = hypot(cityX[i]-cityX[j], cityY[i]-cityY[j]);
            Q.push( cedge(roadCost*L, edge(i,j)) );
         }

      UnionFind uf(N);

      double curCost = 0;
      double minCost = airportCost*N;
      while( !Q.empty() )
      {
         double c = Q.top().first;
         int a = Q.top().second.first;
         int b = Q.top().second.second;
         Q.pop();

         if( uf.Union(a,b) )
         {
            curCost += c;
            minCost = min(minCost, curCost + (uf.size()<=1 ? 0 : uf.size())*airportCost);
         }
      }

      return minCost;
   }
};