読者です 読者をやめる 読者になる 読者になる

解いた問題のソースコードと解説など。


POJ 2253 Frogger

POJ 二分探索 幅優先探索 グラフ
問題

x,y座標が幾つか与えられる。0番目の点から1番目の点に向かって、直接、もしくはその他の点を経由しながら移動する。点から点へのジャンプにかかるコストは点と点のユークリッド距離で表される。移動中にかかる最長のコストを最小化せよ。

やりかた

二分探索で候補となるコストを定めて、そのコストで移動可能かチェックした。チェックの仕方は、候補となるコスト以下のジャンプ(辺)をすべて列挙し、その辺の移動で0番目から1番目に移動できるか調べる方法をとった。

以下汚いソース。

struct path{
  int from, to;
  double d;
  path(){}
  path(int from, int to, double d) : from(from), to(to), d(d) {}
  bool operator<(const path &r)const{
    return d < r.d;
  }
};

int main(int argc, char **argv){
  int N;
  int idx = 0;
  while(scanf("%d", &N), N){
    int x[200], y[200];
    for(int i = 0; i < N; i++) cin >> x[i] >> y[i];
    
    vector<path> pa;
    for(int i = 0; i < N; i++)
      for(int j = i; j < N; j++)
	pa.push_back(path(i, j, sqrt((x[i] - x[j]) * (x[i] - x[j]) + 
				     (y[i] - y[j]) * (y[i] - y[j]))));
    sort(ALL(pa));
    
    double ub = 1e10, lb = 0.0;
    for(int i = 0; i < 100; i++){
      double mid = (ub + lb) * 0.5;
      bool d[200][200];
      FILL(d, false);
      for(int i = 0; i < pa.size(); i++)
	if(mid >= pa[i].d + EPS) 
	  d[pa[i].from][pa[i].to] = d[pa[i].to][pa[i].from] = true;
      
      queue<int> Q;
      Q.push(0);
      vector<bool> vis(N, false);
      vis[0] = true;
      bool reach = false;
      while(!Q.empty()){
	int p = Q.front(); Q.pop();
	if(p == 1){
	  reach = true;
	  break;
	}
	for(int i = 0; i < N; i++){
	  if(d[p][i] && !vis[i]){
	    Q.push(i);
	    vis[i] = true;
	  }
	}
      }
      if(reach) ub = mid;
      else lb = mid;
    }
    printf("Scenario #%d\nFrog Distance = %.3f\n\n", ++idx, ub);
  }
  return 0;
}
しょげないでよBaby 眠れば治る