土下座しながら探索中

主に競技プログラミング

AOJ 1229 : Young, Poor and Busy

AOJ 動的計画法

問題リンク : Young, Poor and Busy | Aizu Online Judge

問題概要 :
けんさんは函館に住んでおり、けいこさんは東京に住んでいる
けんさんとけいこさんは電車を使って合う予定を立てている
電車の時刻表の情報を持っており、その情報は電車が出発する駅の名前、電車の出発時間、電車が到着する駅の名前、電車の到着時間、その電車に乗った際にかかる金額からなる
どこかの駅で二人は待ち合わせをしたい
二人は合流した後、最低でも３０分はその駅で時間を潰す
さらに、けんさんとけいこさんが出発できるのは午前８時以降で午後６時までにそれぞれの住んでいる場所に帰らなければならない
けんさんとけいこさんが上の条件を満たすような電車の移動をした際にかかる金額の最小値を求めよ
そのような移動が不可能な場合は０と出力すること

駅の数は最大１００
電車の情報は最大２０００

解法 :
動的計画法
時刻のうち必要な点は高々４０００個
どの駅に何時に集合するかは全部決めることができる
各出発駅から集合場所に集合時刻までに到達する最小の時間と
集合場所から集合時刻+30分後に出発し各出発駅に帰る時間をあらかじめDPで求める

コード：

#include<bits/stdc++.h>

#define REP(i,s,n) for(int i=s;i<n;i++)
#define rep(i,n) REP(i,0,n)

using namespace std;

struct Info {
  int fromStationID,toStationID;
  int fromTimeID,toTimeID;
  int cost;
};

const int IINF = INT_MAX;
const int MAX_STATION = 100;
const int MAX_EVENT   = 4000;
int   toDest[2][MAX_STATION][MAX_EVENT+10]; // toDest[0][][] <- hakodate, toDest[1][][] <- tokyo, toDest[][stationID][timeID] := ８時からstationIDにtimeIDの時間までに到着する最小
int fromDest[2][MAX_STATION][MAX_EVENT+10]; // fromDest[0][][] <- hakodate, fromDest[1][][] <- tokyo, fromDest[][stationID][timeID] := ６時までにstationIDからtimeIDの時間に出発して帰宅するために必要な金額の最小値

int stationIDIndex;
map<string,int> stationIDTable;
vector<int> T;

void init(){
  stationIDIndex = 0;
  stationIDTable.clear();
  T.clear();
}

inline int convertStringIntoTime(string s){
  return ( ( s[0] - '0' ) * 10 + ( s[1] - '0' ) ) * 60 + ( ( s[3] - '0' ) * 10 + ( s[4] - '0' ) ) ;
}

inline int calcTimeID(int _time) {
  return lower_bound(T.begin(),T.end(),_time) - T.begin();
}

Info convertStringIntoInfo(string context){
  vector<string> buf;
  stringstream ss;
  ss << context;
  while( ss >> context ){
    buf.push_back(context);
  }
  assert( buf.size() == 5 );
  int fromStationID = ( stationIDTable.count(buf[0]) ? stationIDTable[buf[0]] : ( stationIDTable[buf[0]] = stationIDIndex++ ) );
  int   toStationID = ( stationIDTable.count(buf[2]) ? stationIDTable[buf[2]] : ( stationIDTable[buf[2]] = stationIDIndex++ ) );
  int fromTime      = convertStringIntoTime(buf[1]);
  int   toTime      = convertStringIntoTime(buf[3]);
  if( fromTime < convertStringIntoTime("08:00") || toTime > convertStringIntoTime("18:00") ) {
    return (Info){-1,-1,-1,-1,-1};
  }
  T.push_back(fromTime);
  T.push_back(toTime);
  return (Info){fromStationID,toStationID,fromTime,toTime,(atoi)(buf[4].c_str())};
}

bool cmp_to(const Info &a,const Info &b) {
  if( a.toTimeID != b.toTimeID) a.toTimeID < b.toTimeID;
  return a.fromTimeID < b.fromTimeID;
}

bool cmp_from(const Info &a,const Info &b) {
  if( a.fromTimeID != b.fromTimeID ) a.fromTimeID > b.fromTimeID;
  return a.toTimeID > b.toTimeID;
}

void makeToDest(vector<Info> &vec,int hakodateID,int tokyoID,int startTimeID,int endTimeID) {
  assert( startTimeID == 0 );
  rep(i,2) rep(j,stationIDIndex) rep(k,endTimeID+1) toDest[i][j][k] = IINF;
  toDest[0][hakodateID][startTimeID] = toDest[1][tokyoID][startTimeID] = 0;
  sort(vec.begin(),vec.end(),cmp_to);
  int cur = 0;

  REP(timeID,startTimeID,endTimeID+1){
    if( timeID-1 >= startTimeID ) {
      rep(stationID,stationIDIndex){
	rep(j,2){
	  toDest[j][stationID][timeID] = min(toDest[j][stationID][timeID],
					     toDest[j][stationID][timeID-1]);
	}
      }
    }
    while( cur < (int)vec.size() && vec[cur].fromTimeID == timeID ){
      rep(j,2){
	if( toDest[j][vec[cur].fromStationID][timeID] == IINF ) continue;
	toDest[j][vec[cur].toStationID][vec[cur].toTimeID] = min(toDest[j][vec[cur].toStationID][vec[cur].toTimeID],
								 toDest[j][vec[cur].fromStationID][timeID]+vec[cur].cost);
      }
      ++cur;
    }
  }
}

void makeFromDest(vector<Info> &vec,int hakodateID,int tokyoID,int startTimeID,int endTimeID) {
  rep(i,2) rep(j,stationIDIndex) rep(k,endTimeID+1) fromDest[i][j][k] = IINF;
  fromDest[0][hakodateID][endTimeID] = fromDest[1][tokyoID][endTimeID] = 0;
  sort(vec.begin(),vec.end(),cmp_from);
  int cur = 0;
  for(int timeID=endTimeID;timeID>=startTimeID;timeID--){
    if( timeID+1 <= endTimeID ) {
      rep(stationID,stationIDIndex){
	rep(j,2){
	  fromDest[j][stationID][timeID] = min(fromDest[j][stationID][timeID],
					       fromDest[j][stationID][timeID+1]);
	}
      }
    }
    while( cur < (int)vec.size() && vec[cur].toTimeID == timeID ) {
      rep(j,2){
	if( fromDest[j][vec[cur].toStationID][timeID] == IINF ) continue;
	fromDest[j][vec[cur].fromStationID][vec[cur].fromTimeID] = min(fromDest[j][vec[cur].fromStationID][vec[cur].fromTimeID],
								       fromDest[j][vec[cur].toStationID][timeID]+vec[cur].cost);
      }
      ++cur;
    }
  }
}

void compute(vector<Info> &vec){

  if( !stationIDTable.count("Hakodate") || !stationIDTable.count("Tokyo") ) {
    puts("0");
    return;
  }

  int hakodateID   = stationIDTable["Hakodate"];
  int tokyoID      = stationIDTable["Tokyo"];
  int startTimeID  = calcTimeID(convertStringIntoTime("08:00")); 
  int   endTimeID  = calcTimeID(convertStringIntoTime("18:00")); 
  makeToDest(vec,hakodateID,tokyoID,startTimeID,endTimeID);
  makeFromDest(vec,hakodateID,tokyoID,startTimeID,endTimeID);

  int mini = IINF;
  rep(rendezvous,stationIDIndex){
    REP(timeID,startTimeID,endTimeID+1){
      if( toDest[0][rendezvous][timeID] == IINF || toDest[1][rendezvous][timeID] == IINF ) continue;
      int leaveTimeID = lower_bound(T.begin(),T.end(),T[timeID]+30) - T.begin();
      if( leaveTimeID >= (int)T.size() ) continue;
      if( fromDest[0][rendezvous][leaveTimeID] == IINF || fromDest[1][rendezvous][leaveTimeID] == IINF ) continue;
      mini = min(mini,
		 toDest[0][rendezvous][timeID]+toDest[1][rendezvous][timeID]+
		 fromDest[0][rendezvous][leaveTimeID]+fromDest[1][rendezvous][leaveTimeID]);
    }
  }  
  if( mini == IINF ) puts("0");
  else               cout << mini << endl;
}

int main(){
  int n;
  while( cin >> n, n ) {
    init();
    cin.ignore();
    vector<Info> vec;
    rep(i,n){
      string s;
      getline(cin,s);
      Info info = convertStringIntoInfo(s);
      if( info.fromStationID == -1 ) continue;
      vec.push_back(info);
    }
    T.push_back(convertStringIntoTime("08:00"));
    T.push_back(convertStringIntoTime("18:00"));
    sort(T.begin(),T.end());
    T.erase(unique(T.begin(),T.end()),T.end());
    rep(i,(int)vec.size()) {
      vec[i].fromTimeID = calcTimeID(vec[i].fromTimeID);
      vec[i].toTimeID   = calcTimeID(vec[i].toTimeID);
    }
    compute(vec);
  }
  return 0;
}