POJ 2253 Frogger
問題
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; }
Get up! 明日のSUPER ST@R!