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

AOJ2021～2030 - (2012/07/23 (月) 19:08:03) の編集履歴(バックアップ)

---

2021　Princess in Danger

http://judge.u-aizu.ac.jp/onlinejudge/description.jsp?id=2021
毒に倒れたお姫様を助けるために冷凍施設のある町で血液を冷凍しながらお姫様のいる街まで冷凍血液をとどけるグラフの問題。

この問題0分で冷凍施設のある町に到達した場合冷凍可能ということに注意しながら動的計画法で片が付きます。
動的計画法の取る状態は、memo[ある町に血液が到達して][残り冷凍時間]=この状態へ到達する最小タイム
です。
後計算量を抑えるために全ての２つの街の間の最短移動距離をワーシャルフロイド法で求めておくことくらいです。
特に気にする部分のない基本的な問題で私のコードは実行速度で12/82位と極平凡な順位となりました。
速度を求めればコードが分かりにくくなるような気がするのでこのへんが手の打ちどころでしょう。
動的計画法の内部ループを冷凍施設のある街だけループするよう縮めるくらいですかね。

#include<stdio.h>
#include<string.h>
#include<queue>
struct E{
int no,time,coldTime;
bool operator<(const E& e)const{
	return time>e.time;
}
};
void wf(int con[101][101],int n){
//まずはワーシャルフロイド法で全街間の最小距離を求める
int t;
for(int y=0;y<n;y++){
	for(int x=0;x<n;x++){
		if(con[x][y]==-1)continue;
		for(int i=0;i<n;i++){
			if(con[y][i]==-1)continue;
			t=con[x][y]+con[y][i];
			if(con[x][i]==-1||con[x][i]>t){
				con[x][i]=t;
			}
		}
	}
}
}
bool setData(){
int n;//街の数
int m;//スタート時の冷凍時間
int l;//再冷凍可能な街の数
int k;//道路の数
int a;//スタート
int h;//ゴール
int x,y,t;
scanf("%d %d %d %d %d %d",&n,&m,&l,&k,&a,&h);
if(n+m+l+k+a+h==0)return false;
bool isColdCity[101];//冷凍施設のある街の一覧
memset(isColdCity,false,sizeof(isColdCity));
for(int i=0;i<l;i++){
	scanf("%d",&x);
	isColdCity[x]=true;
}
isColdCity[a]=isColdCity[h]=true;
int con[101][101];
memset(con,-1,sizeof(con));
for(int i=0;i<k;i++){
	scanf("%d %d %d",&x,&y,&t);
	con[x][y]=con[y][x]=t;
}
wf(con,n);//全ての街の間の最短距離を求める
//動的計画法で解く
int memo[101][101];//memo[街の番号][血液の冷凍時間]=ここまでの最短タイム
memset(memo,-1,sizeof(memo));//
//printf("scanOK");//適切に読み込み完了
E e,nextE;
e.no=a;
e.coldTime=m;
e.time=0;
std::priority_queue<E> pq;
pq.push(e);
int nextTime;
while(!pq.empty()){
	e=pq.top();
	pq.pop();
	if(e.no==h){
		memo[h][0]=e.time;//仮の答えを入れていく
		break;
	}
	t=memo[e.no][e.coldTime];
	if(t!=-1&&t<=e.time)continue;
	memo[e.no][e.coldTime]=e.time;
	for(int i=0;i<n;i++){
		t=con[e.no][i];
		if(t==-1||t>m||isColdCity[e.no]==false)continue;//同じ街に移動しようとしたか、ｔがｍを超えた
		nextE.no=i;
		if(t<=e.coldTime){
			//冷凍しなくても到達できる
			nextE.time=e.time+t;
			nextE.coldTime=e.coldTime-t;
		}else{
			nextE.time=e.time+t+(t-e.coldTime);//移動時間
			nextE.coldTime=0;
		}
		t=memo[nextE.no][nextE.coldTime];
		if(t!=-1&&t<=nextE.time)continue;
		pq.push(nextE);
	}
}
if(memo[h][0]==-1)printf("Help!\n");
else printf("%d\n",memo[h][0]);
return true;
}
int main(){
while(setData());
}