AOJ1318 Long Distance Taxi

AOJ Volume13

問題リンク Long Distance Taxi

  • 概要

ガソリンが最大capまで積めるタクシーがある。タクシーはガソリン1毎に10km走ることができる。タクシーが町SからTまでガス欠を起こすことなく走るとき、その最短距離を答えよ。辿りつけない場合は-1とせよ。
道路がN本ある。2つの町を結んでおり、その距離はDkmである。両端の町が同じ町であったり、町と町の間に道が2本以上あることはない。また、M個の町にはガソリンスタンドがあり、ガソリンを最大まで補給することができる。最初ガソリンは最大まで入っている。また、町に辿りついた瞬間にガソリンが無くなった場合は、ガス欠を起こす前に辿りついたと考えてよい。
1 <= N <= 3000
1 <= M <= 300
1 <= cap <= 200
0 < D <= 2000

  • 解法

ダイクストラで解きます。
(町、ガソリンの残量)のノードがまず思い付くと思いますが、残量が小数点を含むことになり嬉しくありません。ガソリン1で10km走れるので、cap*10 km走れることになり、(町、後何km走れるか)のノードにすることで整数のみの形に落とせます。あとは、ダイクストラを書くだけです。注意すべきは、Nは道路の数であり、町の数ではないということです。町の数は最大で6000まであることになります。
書いたプログラムがMLEではじかれるかもしれません。プログラムでダイクストラのノードを表す配列をデータセット毎に取っていたら、それはやめましょう。一番最初に最大サイズである6000*2001の配列を取得し、データセット毎に利用する領域だけ初期化する、ということをするといいと思います、実行時間もかなり早くなるでしょう。
TLEがでた場合で、PriorityQueueにノードを渡す時に配列をnew して渡していたとしたら、配列の要素を1つの整数値にして渡すと速くなると思います。配列をnew する処理は意外と重いので。

  • ソース
import java.util.Arrays;
import java.util.Comparator;
import java.util.HashMap;
import java.util.HashSet;
import java.util.Map;
import java.util.PriorityQueue;
import java.util.Scanner;
import java.util.Set;

//Long Distance Taxi
public class AOJ1318 {

	class E{
		int t, c;
		public E(int t, int c) {
			this.t = t;
			this.c = c;
		}
	}
	
	Map<String, Integer> ref;
	int ID, INF = 1<<29, M = 2001;
	int reg(String s){
		if(ref.containsKey(s))return ref.get(s);
		ref.put(s, ID);
		return ID++;
	}

	Set<E>[] adj;
	int[] d;
	boolean[] gas;
	
	@SuppressWarnings("unchecked")
	void run(){
		Scanner sc = new Scanner(System.in);
		d = new int[6000*2001];
		adj = new Set[6000];
		gas = new boolean[6000];
		for(;;){
			int n = sc.nextInt(), m = sc.nextInt(), cap = sc.nextInt();
			if((n|m|cap)==0)break;
			ref = new HashMap<String, Integer>();
			ID = 0;
			int S = reg(sc.next()), T = reg(sc.next());
			for(int i=0;i<6000;i++)adj[i]=new HashSet<E>();
			while(n--!=0){
				int s = reg(sc.next()), t = reg(sc.next()), D = sc.nextInt();
				adj[s].add(new E(t, D)); adj[t].add(new E(s, D));
			}
			Arrays.fill(gas, false);
			while(m--!=0)gas[reg(sc.next())]=true;
			for(int i=0;i<ID;i++)for(int j=0;j<=10*cap;j++)d[i*M+j]=INF;
			PriorityQueue<Integer> q = new PriorityQueue<Integer>(ID, new Comparator<Integer>() {
				public int compare(Integer o1, Integer o2) {
					return d[o1]-d[o2];
				}
			});
			d[S*M+10*cap] = 0;
			q.add(S*M+10*cap);
			int res = -1;
			while(!q.isEmpty()){
				int v = q.poll();
				int p = v/M, c = v%M;
				if(p==T){
					res = d[v]; break;
				}
				for(E e:adj[p]){
					if(c-e.c<0)continue;
					int w = d[v]+e.c;
					if(gas[e.t]){
						if(w < d[e.t*M+10*cap]){
							d[e.t*M+10*cap] = w; q.add(e.t*M+10*cap);
						}
					}
					else{
						if(w < d[e.t*M+c-e.c]){
							d[e.t*M+c-e.c] = w; q.add(e.t*M+c-e.c);
						}
					}
				}
			}
			System.out.println(res);
		}
	}
	
	public static void main(String[] args) {
		new AOJ1318().run();
	}
}