こっちの方がすんなり。
http://arc064.contest.atcoder.jp/tasks/arc064_c
問題
2次元座標上で点Sから点Tに速度1移動したい。
その際、移動した時間分放射線を浴びてしまうが、いくつか円形のバリアがあり、その内部を移動する間は放射線を浴びない。
これらの円形バリアは固定で、その位置(X(v),Y(v))と半径R(v)が与えられる。
最適に移動した場合、放射線を浴びる最短時間を求めよ。
解法
S,Tも半径0のバリアとみなすとやりやすい。
2つのバリアa,bの中心距離をD(a,b)とすると、max(0,D(a,b)-R(a)-R(b))がその間を移動する際にで放射線を浴びる時間となる。
あとは円の中心間の移動について、ダイクストラの要領で最短経路を求める。
ll XS,YS,XT,YT; int N; double X[5050],Y[5050],R[5050]; double D[5050]; void solve() { int i,j,k,l,r,x,y; string s; cin>>X[0]>>Y[0]>>X[1]>>Y[1]; R[0]=R[1]=0; cin>>N; FOR(i,N) { cin>>X[i+2]>>Y[i+2]>>R[i+2]; } N+=2; for(i=1;i<N;i++) D[i]=1e15; priority_queue<pair<double,int>> P; P.push({0,0}); while(P.size()) { double cost=-P.top().first; int cur=P.top().second; P.pop(); if(cost!=D[cur]) continue; FOR(i,N) if(i!=cur) { double d=hypot(X[i]-X[cur],Y[i]-Y[cur])-R[i]-R[cur]; if(d<0) d=0; if(D[i]>D[cur]+d) { D[i]=D[cur]+d; P.push({-D[i],i}); } } } _P("%.12lf\n",D[1]); }
まとめ
今回これが一番コード量が多い。