AOJ2021 Princess in Danger

AOJ Volume20

問題リンク Princess in Danger

  • 解法

基本的には(都市、血液の残り時間)をノードにしたダイクストラです。が、このままだとTLEになります。
工夫1. 評価関数を導入します。「(都市、時間)の値」+「(都市-ゴール)間の最短距離」が小さい順に頂点を訪問します。これは、その状態から少なくとも、ゴールまでの最短距離だけ時間がかかるので、評価関数として使えます。任意の2頂点間の最短距離はワーシャルフロイド法で求めておきます。
工夫2. 辺は隣接リストで表現する
工夫3. 頂点の状態は1つの整数にしておく
工夫4. ノード(i, m)にDで到達したとする。このとき、m' (0<= m' <=m-1)の状態において、D以上のコストがかかっているノード(i, m')があった場合、その状態から始まる探索をしなくてよい。なぜなら、残り時間がより大きいmにそれらより安いコストで到達しているのだから、(i, m)から探索した結果の方が必ず良いに決まっているからです。ただ、これをチェックするのにO(m)かかるのであまり効果的とはいえないかも・・・
Javaだとこれだけの工夫をすればギリギリ間に合います (TimeLimit 16秒に対して15.95秒で通りました 汗)
他のJavaerの方々はどう解いているのでしょうかねぇ

  • ソース
import java.util.ArrayList;
import java.util.Arrays;
import java.util.Comparator;
import java.util.List;
import java.util.PriorityQueue;
import java.util.Scanner;

//Princess in Danger
public class AOJ2021 {

	int[][] dist, wf;
	int INF = 1<<29, P = 107;
	int N, M, L, K, A, H;
	
	class E{
		int t, d;
		public E(int t, int d) {
			this.t = t;
			this.d = d;
		}
	}
	
	@SuppressWarnings("unchecked")
	void run(){
		Scanner sc = new Scanner(System.in);
		for(;;){
			N = sc.nextInt(); M = sc.nextInt(); L = sc.nextInt(); K = sc.nextInt(); A = sc.nextInt(); H = sc.nextInt();
			if((N|M|L|K|A|H)==0)break;
			boolean[] ice = new boolean[N];
			ice[A] = ice[H] = true;
			while(L--!=0)ice[sc.nextInt()] = true;
			List<E>[] es = new ArrayList[N];
			for(int i=0;i<N;i++)es[i]=new ArrayList<E>();
			wf = new int[N][N];
			for(int[]a:wf)Arrays.fill(a, INF);
			while(K--!=0){
				int s = sc.nextInt(), t = sc.nextInt(), d = sc.nextInt();
				wf[s][t] = wf[t][s] = d;
				es[s].add(new E(t, d)); es[t].add(new E(s, d));
			}
			for(int k=0;k<N;k++)for(int i=0;i<N;i++)for(int j=0;j<N;j++)wf[i][j]=Math.min(wf[i][j], wf[i][k]+wf[k][j]);
			dist = new int[N][M+1];
			for(int[]a:dist)Arrays.fill(a, INF);
			for(int i=0;i<=M;i++)dist[A][i] = 0;
			PriorityQueue<Integer> q = new PriorityQueue<Integer>(N, new Comparator<Integer>() {
				public int compare(Integer o1, Integer o2) {
					int a = o1/P, b = o1%P, c = o2/P, d = o2%P;
					return (dist[a][b]+wf[a][H])-(dist[c][d]+wf[c][H]);
				}
			});
			q.add(A*P+M);
			int res = INF;
			while(!q.isEmpty()){
				int v = q.poll();
				int pos = v/P, m = v%P;
				if(pos==H){
					res = dist[pos][m]; break;
				}
				for(E e:es[pos]){
					for(int t=0;t+m<=M;t++){
						if(t>0&&!ice[pos])break;
						int nm = t+m-e.d;
						if(nm<0)continue;
						int w = dist[pos][m]+t+e.d;
						if(w<dist[e.t][nm]){
							q.remove(e.t*P+nm); dist[e.t][nm] = w;
							int r = nm-1;
							while(r>=0&&w<=dist[e.t][r]){
								q.remove(e.t*P+r);  dist[e.t][r] = w; r--;
							}
							q.add(e.t*P+nm);
						}
					}
				}
				
			}
			System.out.println(res==INF?"Help!":res);
		}
	}

	public static void main(String[] args) {
		new AOJ2021().run();
	}
}