テキトーなメモ帳

テキトーなメモ帳

PKU 2067 Young, Poor and Busy

http://www.ipsj.or.jp/07editj/promenade/
の「どこで会える」を参考(いや、ほとんど写経)に書きました。

AOJ:1229と同一の問題ですが、AOJの方ではruntime errorを起こしてしまいました。


やり方は
・函館/東京を起点として、ある駅にある時刻までに到着するためには最小でいくら費用がかかるか。
・ある駅を出発して、東京/函館に行くとして、ある時刻まである駅に居るためには最小でいくら費用がかかるか。
の4つの表をDPでつくる→表をみて最小値を計算。

#define _USE_MATH_DEFINES
#include <iostream>
#include <sstream>
#include <cmath>
#include <algorithm>
#include <queue>
#include <stack>
#include <limits>
#include <map>
#include <string>
#include <cstring>
#include <set>
#include <deque>

using namespace std;

typedef long long ll;
typedef pair<int,int> P;

static const int BIAS = (18-8)*60;
static const int INF = 10000000;

int h2m(char* time){
	int h,m;
	sscanf(time,"%d:%d",&h,&m);
	return h*60+m;
}

class Train{
private:
	string mFrom;
	string mTo;
	int mDpt;
	int mArv;
	int mFare;

public:
	Train(char* from,char* to,int dpt,int arv,int fare){
		mFrom = from;
		mTo = to;
		mDpt= dpt;
		mArv= arv;
		mFare=fare;
	}
	Train():mFrom(""),mTo(""),mDpt(0),mArv(0),mFare(0){}

	string getFrom() const{return mFrom;}
	string getTo() const{return mTo;}
	int getDpt() const{return mDpt;}
	int getArv() const{return mArv;}
	int getFare() const{return mFare;}

};

class arv_order{
public:
	bool operator()(const Train train1, const Train train2) const {
		return train1.getArv() < train2.getArv();
	}
};

int change(const vector<Train>& tv,int p,int st,int dpt_time,map<string,int> city){
	for(;p>=0;p--){
		if(city[tv[p].getTo()] == st 
			&& tv[p].getArv() <= dpt_time) break;
	}

	return p;
}

void make_table(int** v,int org,const vector<Train>& tv,map<string,int> city){

	for(int i=0; i<city.size();i++){
		v[i][0] = INF;
	}

	v[org][0] = 0;

	for(int i=0;i<tv.size(); i++){
		for(int j=0;j<city.size();j++){
			v[j][i+1] = v[j][i];
		}

		int a = change(tv,i-1,city[tv[i].getFrom()],tv[i].getDpt(),city);

		v[city[tv[i].getTo()]][i+1] = min(v[city[tv[i].getTo()]][i],
			tv[i].getFare() + v[city[tv[i].getFrom()]][a+1]);
	}	
}

int calc_cost(int city,const vector<Train>& trains,const vector<Train>& rtrains,
	int** from_hak,int** from_tok,int** to_hak,int** to_tok){
	int a = 0;
	int d = trains.size() - 1;
	int min_c = INF;

	for(int d=trains.size()-1; d>=0; d--){
		for(int a=0;a<trains.size();a++){
			int stay = (BIAS - rtrains[d].getArv()) - trains[a].getArv();
			if(stay < 30) continue;
			int c = from_hak[city][a+1]
			+ from_tok[city][a+1]
			+ to_hak[city][d+1]
			+ to_tok[city][d+1];

			min_c = min(min_c,c);
		}
	}

	return min_c;	
}

int main(){
	int n;
	while(~scanf("%d",&n)){
		if(n==0) break;
		vector<Train> rtrains;
		vector<Train> trains;
		map<string,int> city;

		int** from_hak;
		int** from_tok;
		int** to_hak;
		int** to_tok;

		for(int i=0,j=0;i<n;i++){			
			char from[64],dpt[64],to[64],arv[64];
			int fare;
			scanf("%s %s %s %s %d",from,dpt,to,arv,&fare);
			//printf("time:%d\n",getsec(src_time));
			if(h2m(dpt) < 8*60 || h2m(arv) > 18*60) continue;
			
			if(city.find(from)==city.end()){
				city[from]=j++;
			}
			rtrains.push_back(Train(to,from,BIAS-h2m(arv),BIAS-h2m(dpt),fare));
			trains.push_back(Train(from,to,h2m(dpt),h2m(arv),fare));
		}

		from_hak = new int*[city.size()+1];
		from_tok = new int*[city.size()+1];
		to_hak = new int*[city.size()+1];
		to_tok = new int*[city.size()+1];

		for(int i=0;i<city.size()+1;i++){
			from_hak[i] = new int[trains.size()+1];
			from_tok[i] = new int[trains.size()+1];
			to_hak[i] = new int[trains.size()+1];
			to_tok[i] = new int[trains.size()+1];
		}
			
		sort(trains.begin(),trains.end(),arv_order());
		sort(rtrains.begin(),rtrains.end(),arv_order());

		make_table(from_hak,city["Hakodate"],trains,city);
		make_table(from_tok,city["Tokyo"],trains,city);
		make_table(to_hak,city["Hakodate"],rtrains,city);
		make_table(to_tok,city["Tokyo"],rtrains,city);

		int min_cost = INF;

		for(int i=0;i<city.size();i++){
			int cost = calc_cost(i,trains,rtrains,
				from_hak,from_tok,to_hak,to_tok);
			min_cost = min(min_cost,cost);
		}

		printf("%d\n",min_cost >= INF ? 0 : min_cost);

		for(int i=0;i<city.size()+1;i++){
			delete[] from_hak[i];
			delete[] from_tok[i];
			delete[] to_hak[i];
			delete[] to_tok[i];
		}

		delete[] from_hak;
		delete[] from_tok;
		delete[] to_hak;
		delete[] to_tok;

	}

	return 0;
}