SRM461 Div1 Medium

500
ある町からある町へ直接行くために必要な新設の町の数は割り算すれば分かる。
[町][追加した町の数]でダイクストラ。
頂点数が大きい。ちょっと手を抜いて実装してタイムリミット出してしまった。

struct State{
  double cost;
  int node, add;
  State(double c, int n, int a) 
    : cost(c), node(n), add(a) {}
};
inline
bool operator < (const State &a, const State &b)
{
  if( a.cost != b.cost )return a.cost > b.cost;
  if( a.add != b.add )return a.add > b.add;
  return a.node > b.node;
}

const double inf = 1e255;

const int ADD = 2001;
double cost[51][ADD];
bool vis[51][ADD];

double g[51][51];
int add[51][51];

int solve(const int node, double maxTravel)
{
  priority_queue<State> q;
  fill( &vis[0][0], &vis[50][ADD], false );
  fill( &cost[0][0], &cost[50][ADD], inf );
  
  cost[0][0] = 0;

  for( q.push( State(0, 0, 0) ); q.size(); ){
    State n = q.top();
    q.pop();
    if( vis[n.node][n.add] )continue;
    vis[n.node][n.add] = true;
    cost[n.node][n.add] = n.cost;
    for(int i=0; i<node; ++i){
      double c = n.cost + g[n.node][i];
      int a = add[n.node][i] + n.add;      
      if( vis[i][a] )continue;
      if( ADD <= a )continue;
      if( maxTravel < c )continue;
      if( c < cost[i][a] ){
        cost[i][a] = c;
        q.push( State(c, i, a) );
      }
    }
  }

  for(int i=0; i<ADD; ++i){
    if( cost[node-1][i] < maxTravel )return i;
  }
  return -1;
}

class BuildingCities {
public:
  int findMinimumCities(int maxDirect, int maxTravel, vector <int> cityX, vector <int> cityY) {
    
    const int node = cityX.size();

    for(int i=0; i<node; ++i){
      for(int j=0; j<node; ++j){
        if( i == j )g[i][j] = inf;
        else{
          double x = cityX[i] - cityX[j];
          double y = cityY[i] - cityY[j];
          g[i][j] = sqrt( x * x +  y * y );
          add[i][j] = (g[i][j] - EPS) / (double)maxDirect;
        }
      }
    }

    return solve(node, maxTravel);
  }
};