「aoj2231～2240」の編集履歴（バックアップ）一覧に戻る

aoj2231～2240 - (2013/02/08 (金) 18:55:25) のソース

*2233 Carrot Tour
http://judge.u-aizu.ac.jp/onlinejudge/description.jsp?id=2233
兎が都市を回って人参をもらってくる問題。

解法
兎が前にいた都市今いる都市の組を点に見立ててグラフとして解きます。
人参の個数を一つずつインクリメントしながら人参ｎ個で前にいた都市a今いる都市ｂとして動的計画法で計算していけば答えが出ます。
もっと速度が出るかと思ったら意外と速度が出ませんでした。





 #include<stdio.h>
 #include<vector>
 #include<queue>
 #include<map>
 #include<math.h>
 #include<iostream>
 
 struct rMove{
 	int oldCity,nowCity;
 	long double len;
 };
 
 int main(){
 	long double xs[21],ys[21];
 	int n;
 	long double r,theta;
 	scanf("%d",&n);
	if(n==1){
 		printf("0\n");
 		return 0;
 	}
 	std::cin>>r>>theta;
 	theta=cos(theta/180.0*M_PI);
 	for(int i=0;i<n;i++){
 		std::cin>>xs[i]>>ys[i];
 	}
 	std::vector<int> moveOKs[21][21];//moveOKs[前いた都市][今いる都市]="次にいける都市のリスト"
 	long double dx1,dx2,dy1,dy2;
 	for(int i=0;i<n;i++){
 		//前の都市
 		for(int j=0;j<n;j++){
 			//今いる都市
 			if(i==j)continue;
 			for(int k=0;k<n;k++){
 				//次の都市
 				if(i==k||j==k)continue;
 				dx1=xs[j]-xs[i];
 				dy1=ys[j]-ys[i];
 				dx2=xs[k]-xs[j];
 				dy2=ys[k]-ys[j];
 				double cos1=(dx1*dx2+dy1*dy2)/(hypot(dx1,dy1)*hypot(dx2,dy2));
 				if(cos1>=theta&&hypot(dx2,dy2)<=r){
 					moveOKs[i][j].push_back(k);
 				}
 			}
 		}
 	}
 	std::queue<rMove> qu;
  	rMove rm;
 	rm.oldCity=0;
 	for(int i=1;i<n;i++){
 		rm.len=hypot(xs[i]-xs[0],ys[i]-ys[0]);
 		rm.nowCity=i;
 		if(rm.len<=r){
 			qu.push(rm);
 		}
 	}
 	int ans=0;
 	std::map<int,double> getMemo[21];//[前にいた都市][今いる都市]=最短移動距離
 	while(qu.empty()==false){
 		double len;
 		ans++;
 		while(qu.empty()==false){
  			rm=qu.front();
 			qu.pop();
 			if(rm.len>r)continue;
 			for(int i=0;i<moveOKs[rm.oldCity][rm.nowCity].size();i++){
 				int no=moveOKs[rm.oldCity][rm.nowCity][i];
 				double len=rm.len+hypot(xs[rm.nowCity]-xs[no],ys[rm.nowCity]-ys[no]);
 				if(len>r)continue;
 				if(getMemo[rm.nowCity].find(no)==getMemo[rm.nowCity].end()||getMemo[rm.nowCity][no]>len){
 					getMemo[rm.nowCity][no]=len;
 				}
  			}
 		}
 		for(int i=0;i<n;i++){
 			for(int j=0;j<n;j++){
 				if(getMemo[i].find(j)!=getMemo[i].end()){
 					rm.oldCity=i;
 					rm.nowCity=j;
 					rm.len=getMemo[i][j];
 					qu.push(rm);
  				}
 			}
 		}
 		for(int i=0;i<n;i++)getMemo[i].clear();
 	}
 	
 	printf("%d\n",ans);
 }