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

AOJ2151～2160 - (2012/07/26 (木) 16:38:17) のソース

*2151　Brave Princess Revisited
http://judge.u-aizu.ac.jp/onlinejudge/description.jsp?id=2151
限られた予算で護衛を雇いながら少しでも安全にお姫様を目的地まで送り届ける問題。

解法
私なりに考えた解法は以下の通りです。
予算の値が小さいことを利用して以下の手法で解きます。
memo[今いる街][残り予算]=この状態にいたったときの最小の刺客人数。
今いる街と残り予算の二つの組で一点と定義されるグラフに対し動的計画法を適用します。
後は少し高速化の魔法を振りかけてコード実行速度81位中2位タイの出来上がりです。



 #include<stdio.h>
 #include<string.h>
 #include<queue>
 #include<vector>
 struct State{
	int no,danger,L;//今いる街、襲ってきた刺客の数,残り予算
	bool operator<(const State& s)const{
		return danger>s.danger;
	}
 };
 struct E{
	int danger,len,next;
 };
 void setData(int n,int m,int l){
	int memo[101][101];//memo[今いる街][残り予算]=この状態での最小刺客数
	memset(memo,-1,sizeof(memo));//初めては-1
	int a,b;
	E e;
	std::vector<E> con[101];
	for(int i=0;i<m;i++){
		scanf("%d %d %d %d",&a,&b,&e.len,&e.danger);
		e.next=b;
		con[a].push_back(e);
		e.next=a;
		con[b].push_back(e);//問題をグラフに翻訳する
	}
	//printf("scanOK");
	State s,nextS;
	s.no=1;
	s.danger=0;
	s.L=l;
	std::priority_queue<State> pQ;
	pQ.push(s);
	int t1;
	//問題を定石通り動的計画法で解く
	while(!pQ.empty()){
		s=pQ.top();
		pQ.pop();
		if(s.no==n)break;
		t1=memo[s.no][s.L];
		if(t1!=-1&&t1<s.danger)continue;
		memo[s.no][s.L]=s.danger;
		int size=con[s.no].size();
		for(int i=0;i<size;i++){			
			e=con[s.no][i];
			nextS.no=e.next;//次の街を設定
			//護衛を雇えるなら雇って移動する
			if(s.L>=e.len){
				nextS.L=s.L-e.len;//予算を減らす
				nextS.danger=s.danger;
				t1=memo[nextS.no][nextS.L];
				if(t1==-1||(t1!=-1&&t1>nextS.danger)){
					memo[nextS.no][nextS.L]=nextS.danger;
					pQ.push(nextS);
				}
				//次は護衛を雇わない使わない場合
			}
			//先を考えるか予算不足で護衛を雇わないで移動する
			nextS.L=s.L;//護衛を雇わないので予算は減らない
			nextS.danger=s.danger+e.danger;//護衛を雇わないので襲われる数が増える
			t1=memo[nextS.no][nextS.L];
			if(t1!=-1&&t1<=nextS.danger)continue;
			memo[nextS.no][nextS.L]=nextS.danger;
			pQ.push(nextS);
		}
	}
	printf("%d\n",s.danger);
 }
 int main(){
	int n,m,l;
	while(1){
		scanf("%d %d %d",&n,&m,&l);
		if(n+m+l==0)break;
		setData(n,m,l);
	}
 }