2067-Young, Poor and Busy

PKU

問題概要

東京と函館に住んでいる友人同士がどこかの駅で会うことになった．
時刻表が与えられるので以下の条件を満たす旅行計画のうち最も安価なものを答えよ．

  • 早くとも6:00に出発し，遅くとも18:00にそれぞれ元の駅に戻る
  • 30分は会う時間を確保する

解法

動的計画法
函館,東京を6:00に出た時Vにある時刻にアクセスするための最小コスト
と
函館，東京へある18:00までにある時間から帰るための最小コスト
を求め，4つ和の最小値を求める．

実装(C++)

割と冗長なコード

#include <iostream>
#include <cstdio>
#include <map>
#include <vector>
using namespace std;
const int INF=99999999;
#define LETMIN(a,b) a=min((a),(b));
int get_time(const string &a){
	int h,m;
	sscanf(a.c_str(),"%d:%d",&h,&m);
	return h*60+m;
}
struct Cityname{
	map<string,int> m;
	int operator()(const string &a){
		if(m.find(a)==m.end()){
			int t=m.size();
			m[a]=t;
		}
		return m[a];
	}
	Cityname(){
		(*this)("Hakodate");
		(*this)("Tokyo");
	}
};
struct Line{//路線
	int src,dst;
	int stime,dtime;
	int cost;
};
bool input(vector<Line> &lines,int &V){
	int n;
	if(!(cin>>n))return false;
	if(n==0)return false;
	lines=vector<Line>(n);
	Cityname tmp;
	for(int i=0;i<n;i++){
		string a,b,c,d;int e;
		cin>>a>>b>>c>>d>>e;
		lines[i]=(Line){tmp(a),tmp(c),get_time(b),get_time(d),e};
	}
	V=tmp.m.size();
	return true;
}
int main() {
	vector<Line> lines;int V;
	while(input(lines,V)){
		int min_cost1[2][V][24*60];//函館,東京からVにk分にアクセスするための最小コスト
		vector<int> o_train[V][24*60];//Vにある時間に発車する電車
		for(int i=0;i<(int)lines.size();i++){
			o_train[lines[i].src][lines[i].stime].push_back(i);
		}
		for(int i=0;i<V;i++)for(int j=0;j<60*24;j++){
			min_cost1[0][i][j]=min_cost1[1][i][j]=INF;
		}
		min_cost1[0][0][8*60]=0;
		min_cost1[1][1][8*60]=0;
		for(int k=0;k<2;k++){
			for(int j=1;j<60*24;j++){
				for(int i=0;i<V;i++){
					LETMIN(min_cost1[k][i][j],min_cost1[k][i][j-1]);
					for(int c=0;c<(int)o_train[i][j].size();c++){
						Line &t=lines[o_train[i][j][c]];
						LETMIN(min_cost1[k][t.dst][t.dtime],min_cost1[k][i][j]+t.cost);
					}
				}
			}
		}

		int min_cost2[2][V][24*60];//函館，東京へある18:00までにある時間から帰るための最小コスト
		vector<int> i_train[V][24*60];//Vにある時間に到着する電車
		for(int i=0;i<(int)lines.size();i++){
			i_train[lines[i].dst][lines[i].dtime].push_back(i);
		}
		for(int i=0;i<V;i++)for(int j=0;j<60*24;j++){
			min_cost2[0][i][j]=min_cost2[1][i][j]=INF;
		}
		min_cost2[0][0][18*60]=0;
		min_cost2[1][1][18*60]=0;
		for(int k=0;k<2;k++){
			for(int j=60*24-2;j>=0;j--){
				for(int i=0;i<V;i++){
					LETMIN(min_cost2[k][i][j],min_cost2[k][i][j+1]);
					for(int c=0;c<(int)i_train[i][j].size();c++){
						Line &t=lines[i_train[i][j][c]];
						LETMIN(min_cost2[k][t.src][t.stime],min_cost2[k][i][j]+t.cost);
					}
				}
			}
		}
		int ans=INF;
		for(int i=0;i<V;i++){
			for(int j=0;j<24*60-30;j++){
				LETMIN(ans,min_cost1[0][i][j]+min_cost1[1][i][j]+min_cost2[0][i][j+30]+min_cost2[1][i][j+30]);
			}
		}
		if(ans==INF){
			cout<<0<<endl;
		}else{
			cout<<ans<<endl;
		}
	}
	return 0;
}