AOJ1229 Young, Poor and Busy

問題リンク Young, Poor and Busy

• 概要

KenとKeikoはそれぞれHakodateとTokyoにいる。2人はどこの都市でもいい(Hakodate,Tokyoでもよい)ので合流し、30分以上一緒にいた後、それぞれの都市に帰りたい。2人はAM08:00以降に出発でき、PM18:00までには帰らなければならない。このとき、2人の交通費のコストの合計を最小にせよ。条件を満たすことができない場合は0と答えよ。
電車の情報はM個ある。始点、出発時間、終点、到着時間、コストの情報がある。
都市数<=100
M<=2000

• 解法

合流する都市を1つ決め、その都市に向かう最小コストと、その都市から帰る最小コストをそれぞれ求めるのが基本方針です。
この問題では時間も考慮しなければならないのが厄介です。まず、合流する都市に向かう最小コストをDPで求めます。
go1[i][j]: Hakodateから出発し、時刻 j までに都市 i に到着するための最小コスト
go2[i][j]: Tokyoから出発し、時刻 j までに都市 i に到着するための最小コスト
とします。
この表を埋めるためには,時刻 j 以前についてDP表が埋まっていればいいので、路線を到着時間でソートして埋めていきます。漸化式は
go1[i][j] = min{go1[i][j], go1[出発駅][出発時間]+コスト}
となります。また、都市 i に時刻 j に到着できたら、j 以降の時刻にもそのコストで到着できることになるので、それについても更新します。
DP表を埋めることができたら、合流都市を1つ決めます。都市を決める際にいつ合流するかの情報も必要なので、(都市数)*(合流時間)の対になるので組み合わせが大きくなってしまいます。が、2人が時間tに合流したとして、t+1とかt+2とかについて考慮するのは無駄です。つまりいつ合流するかは電車の到着時間についてのみ考えれば十分なので、合流都市と集合時間の組み合わせは路線の数Mだけに抑えられます。
合流都市と時間を決めたら、都市から帰るコストをダイクストラで求めます。

• ソース

import java.util.ArrayList;
import java.util.Arrays;
import java.util.Comparator;
import java.util.HashMap;
import java.util.List;
import java.util.Map;
import java.util.PriorityQueue;
import java.util.Scanner;

//Young, Poor and Busy
public class AOJ1229 {

	int START = 60*8;
	int FINISH = 60*18;
	int INF = 1<<29;
	
	//都市を番号で管理する仕組み
	int ID;
	Map<String, Integer> ref;
	int get(String s){
		if(ref.containsKey(s))return ref.get(s);
		ref.put(s, ID);
		return ID++;
	}
	//HH:MMを分に変換
	int time(String s){
		String[] t = s.split(":");
		return Integer.parseInt(t[0])*60+Integer.parseInt(t[1]);
	}
	
	int[][] dist;
	
	//辺クラス 到着時間の昇順にソートできる
	class E implements Comparable<E>{
		int s, t, leave, arrive, cost;
		public E(int s, int t, int leave, int arrive, int cost) {
			this.s = s;
			this.t = t;
			this.leave = leave;
			this.arrive = arrive;
			this.cost = cost;
		}
		public int compareTo(E o) {
			return arrive-o.arrive;
		}
	}
	
	//時間arrive以降に都市startを出発し、18:00までに都市goalに到着するときの最小コスト
	int dijkstra(int start, int arrive, int goal){
		dist = new int[ID][FINISH+1];
		for(int[]a:dist)Arrays.fill(a, INF);
		dist[start][arrive] = 0;
		PriorityQueue<int[]> q = new PriorityQueue<int[]>(ID, new Comparator<int[]>() {
			public int compare(int[] o1, int[] o2) {
				return dist[o1[0]][o1[1]]-dist[o2[0]][o2[1]];
			}
		});
		q.add(new int[]{start, arrive});
		while(!q.isEmpty()){
			int[] a = q.poll();
			int v = a[0];
			int t = a[1];
			if(FINISH<t)continue;
			if(v==goal)return dist[goal][t];
			//都市vを始点とする辺だけ見る
			for(E e:l[v]){
				if(FINISH<e.arrive||e.leave<t)continue;
				int w = dist[v][t] + e.cost;
				if(w<dist[e.t][e.arrive]){
					dist[e.t][e.arrive] = w;
					q.add(new int[]{e.t, e.arrive});
					//都市vに時間arriveにコストwで到着できた = arrive〜FINISHの時間についてもコストwで到着できるということ
					for(int j=e.arrive;j<=FINISH;j++)dist[e.t][j] = Math.min(dist[e.t][j], dist[e.t][e.arrive]);
				}
			}
		}
		//そのような経路はない
		return INF;
	}
	
	List<E>[] l;
	
	@SuppressWarnings("unchecked")
	void run(){
		Scanner sc = new Scanner(System.in);
		for(;;){
			int m = sc.nextInt();
			if(m==0)break;
			ID = 0; ref = new HashMap<String, Integer>();
			//HakodateとTokyoは必ずあるので0, 1を割り振っておく
			get("Hakodate"); get("Tokyo");
			E[] e = new E[m];
			l = new ArrayList[100];
			for(int i=0;i<100;i++)l[i]=new ArrayList<E>();
			for(int i=0;i<m;i++){
				int s = get(sc.next());
				int a = time(sc.next());
				int t = get(sc.next());
				int b = time(sc.next());
				int c = sc.nextInt();
				e[i] = new E(s, t, a, b, c);
				l[s].add(e[i]);
			}
			Arrays.sort(e);
			//go1[i][j]: 時刻jまでにHakodateから都市iへ到着するための最小コスト
			int[][] go1 = new int[ID][FINISH+1];
			for(int[]a:go1)Arrays.fill(a, INF);
			for(int j=START;j<=FINISH;j++)go1[0][j]=0;
			//go2[i][j]: 時刻jまでにTokyoから都市iへ到着するための最小コスト
			int[][] go2 = new int[ID][FINISH+1];
			for(int[]a:go2)Arrays.fill(a, INF);
			for(int j=START;j<=FINISH;j++)go2[1][j]=0;
			//DPを埋める
			for(E r:e){
				//18:00以降に到着するような路線は考えなくていい
				if(r.arrive>FINISH)break;
				//この路線に乗るには都市sに路線の出発時刻までに到着していればいい
				go1[r.t][r.arrive] = Math.min(go1[r.t][r.arrive], go1[r.s][r.leave]+r.cost);
				go2[r.t][r.arrive] = Math.min(go2[r.t][r.arrive], go2[r.s][r.leave]+r.cost);
				//時刻arrive以降についても更新をかける
				for(int j=r.arrive;j<=FINISH;j++){
					go1[r.t][j] = Math.min(go1[r.t][j], go1[r.t][r.arrive]);
					go2[r.t][j] = Math.min(go2[r.t][j], go2[r.t][r.arrive]);
				}
			}
			int min = INF;
			//2人が会える候補は高々m個
			for(E r:e){
				if(FINISH<r.arrive||FINISH<r.arrive+30)continue;
				int res = go1[r.t][r.arrive] + go2[r.t][r.arrive];
				if(INF<res)continue;
				res += dijkstra(r.t, r.arrive+30, 0) + dijkstra(r.t, r.arrive+30, 1);
				min = Math.min(min, res);
			}
			System.out.println(min==INF?0:min);
		}
	}
	
	public static void main(String[] args) {
		new AOJ1229().run();
	}
}