4fd800b3a8 2011-02-23        kinaba: #include <iostream>
4fd800b3a8 2011-02-23        kinaba: #include <sstream>
4fd800b3a8 2011-02-23        kinaba: #include <iomanip>
4fd800b3a8 2011-02-23        kinaba: #include <vector>
4fd800b3a8 2011-02-23        kinaba: #include <string>
4fd800b3a8 2011-02-23        kinaba: #include <map>
4fd800b3a8 2011-02-23        kinaba: #include <set>
4fd800b3a8 2011-02-23        kinaba: #include <algorithm>
4fd800b3a8 2011-02-23        kinaba: #include <numeric>
4fd800b3a8 2011-02-23        kinaba: #include <iterator>
4fd800b3a8 2011-02-23        kinaba: #include <functional>
4fd800b3a8 2011-02-23        kinaba: #include <complex>
4fd800b3a8 2011-02-23        kinaba: #include <queue>
4fd800b3a8 2011-02-23        kinaba: #include <stack>
4fd800b3a8 2011-02-23        kinaba: #include <cmath>
4fd800b3a8 2011-02-23        kinaba: #include <cassert>
4fd800b3a8 2011-02-23        kinaba: #include <cstring>
4fd800b3a8 2011-02-23        kinaba: using namespace std;
4fd800b3a8 2011-02-23        kinaba: typedef long long LL;
4fd800b3a8 2011-02-23        kinaba: typedef complex<double> CMP;
4fd800b3a8 2011-02-23        kinaba: 
4fd800b3a8 2011-02-23        kinaba: class TheAirTripDivOne { public:
4fd800b3a8 2011-02-23        kinaba: 	struct edge {
4fd800b3a8 2011-02-23        kinaba: 		int to;
4fd800b3a8 2011-02-23        kinaba: 		LL F, T, P;
4fd800b3a8 2011-02-23        kinaba: 	};
4fd800b3a8 2011-02-23        kinaba: 	int find(int n, vector <string> flights, int time)
4fd800b3a8 2011-02-23        kinaba: 	{
4fd800b3a8 2011-02-23        kinaba: 		vector< vector<edge> > e(n);
4fd800b3a8 2011-02-23        kinaba: 		{
4fd800b3a8 2011-02-23        kinaba: 			string input = accumulate(flights.begin(), flights.end(), string(""));
4fd800b3a8 2011-02-23        kinaba: 			stringstream sin(input);
4fd800b3a8 2011-02-23        kinaba: 			for(string line; sin>>line;) {
4fd800b3a8 2011-02-23        kinaba: 				stringstream sin(line);
4fd800b3a8 2011-02-23        kinaba: 				int a,b; LL f,t,p; char _;
4fd800b3a8 2011-02-23        kinaba: 				sin >> a >> _ >> b >> _ >> f >> _ >> t >> _ >> p;
4fd800b3a8 2011-02-23        kinaba: 				edge eg = {b-1,f,t,p};
4fd800b3a8 2011-02-23        kinaba: 				e[a-1].push_back(eg);
4fd800b3a8 2011-02-23        kinaba: 			}
4fd800b3a8 2011-02-23        kinaba: 		}
4fd800b3a8 2011-02-23        kinaba: 
4fd800b3a8 2011-02-23        kinaba: 		int lf=0, ri=1000000001;
4fd800b3a8 2011-02-23        kinaba: 		while( ri-lf>1 )
4fd800b3a8 2011-02-23        kinaba: 		{
4fd800b3a8 2011-02-23        kinaba: 			int c = (lf+ri)/2;
4fd800b3a8 2011-02-23        kinaba: 			(ok(n,e,c,time) ? lf : ri) = c;
4fd800b3a8 2011-02-23        kinaba: 		}
4fd800b3a8 2011-02-23        kinaba: 		return lf ? lf : -1;
4fd800b3a8 2011-02-23        kinaba: 	}
4fd800b3a8 2011-02-23        kinaba: 	bool ok(int n, vector< vector<edge> >& e, LL transfer, LL TL)
4fd800b3a8 2011-02-23        kinaba: 	{
4fd800b3a8 2011-02-23        kinaba: 		typedef int vert;
4fd800b3a8 2011-02-23        kinaba: 		typedef LL cost;
4fd800b3a8 2011-02-23        kinaba: 		typedef pair<cost,int> cedge;
4fd800b3a8 2011-02-23        kinaba: 		priority_queue<cedge, vector<cedge>, greater<cedge> > Q;
4fd800b3a8 2011-02-23        kinaba: 		set<vert> V;
4fd800b3a8 2011-02-23        kinaba: 		Q.push( cedge(0,0) );
4fd800b3a8 2011-02-23        kinaba: 		while( !Q.empty() )
4fd800b3a8 2011-02-23        kinaba: 		{
4fd800b3a8 2011-02-23        kinaba: 			cost c = Q.top().first;
4fd800b3a8 2011-02-23        kinaba: 			vert v = Q.top().second;
4fd800b3a8 2011-02-23        kinaba: 			Q.pop();
4fd800b3a8 2011-02-23        kinaba: 			if( V.count(v) )
4fd800b3a8 2011-02-23        kinaba: 				continue;
4fd800b3a8 2011-02-23        kinaba: 			if( v == n-1 )
4fd800b3a8 2011-02-23        kinaba: 				return true;
4fd800b3a8 2011-02-23        kinaba: 			V.insert(v);
4fd800b3a8 2011-02-23        kinaba: 			vector<edge>& ne = e[v];
4fd800b3a8 2011-02-23        kinaba: 			for(int i=0; i<ne.size(); ++i)
4fd800b3a8 2011-02-23        kinaba: 			{
4fd800b3a8 2011-02-23        kinaba: 				vert u = ne[i].to;
4fd800b3a8 2011-02-23        kinaba: 				LL F=ne[i].F, T=ne[i].T, P=ne[i].P;
4fd800b3a8 2011-02-23        kinaba: 				LL t = nextTime(c, F, P, v==0 ? 0 : transfer);
4fd800b3a8 2011-02-23        kinaba: //				cerr<<c<<" "<<F<<" "<<P<<" "<<transfer<<" !! "<<t<<endl;
4fd800b3a8 2011-02-23        kinaba: 				if( !V.count(u) && t+T<=TL )
4fd800b3a8 2011-02-23        kinaba: 					Q.push( cedge(t+T, u) );
4fd800b3a8 2011-02-23        kinaba: 			}
4fd800b3a8 2011-02-23        kinaba: 		}
4fd800b3a8 2011-02-23        kinaba: 		return false;
4fd800b3a8 2011-02-23        kinaba: 	}
4fd800b3a8 2011-02-23        kinaba: 
4fd800b3a8 2011-02-23        kinaba: 	LL nextTime(LL cur, LL F, LL P, LL transfer)
4fd800b3a8 2011-02-23        kinaba: 	{
4fd800b3a8 2011-02-23        kinaba: 		cur += transfer;
4fd800b3a8 2011-02-23        kinaba: 		if( cur <= F )
4fd800b3a8 2011-02-23        kinaba: 			return F;
4fd800b3a8 2011-02-23        kinaba: 		return (cur-F)%P==0 ? cur : ((cur-F)/P+1)*P+F;
4fd800b3a8 2011-02-23        kinaba: 	}
4fd800b3a8 2011-02-23        kinaba: };
4fd800b3a8 2011-02-23        kinaba: 
4fd800b3a8 2011-02-23        kinaba: // BEGIN CUT HERE
4fd800b3a8 2011-02-23        kinaba: #include <ctime>
4fd800b3a8 2011-02-23        kinaba: double start_time; string timer()
4fd800b3a8 2011-02-23        kinaba:  { ostringstream os; os << " (" << int((clock()-start_time)/CLOCKS_PER_SEC*1000) << " msec)"; return os.str(); }
4fd800b3a8 2011-02-23        kinaba: template<typename T> ostream& operator<<(ostream& os, const vector<T>& v)
4fd800b3a8 2011-02-23        kinaba:  { os << "{ ";
4fd800b3a8 2011-02-23        kinaba:    for(typename vector<T>::const_iterator it=v.begin(); it!=v.end(); ++it)
4fd800b3a8 2011-02-23        kinaba:    os << '\"' << *it << '\"' << (it+1==v.end() ? "" : ", "); os << " }"; return os; }
4fd800b3a8 2011-02-23        kinaba: void verify_case(const int& Expected, const int& Received) {
4fd800b3a8 2011-02-23        kinaba:  bool ok = (Expected == Received);
4fd800b3a8 2011-02-23        kinaba:  if(ok) cerr << "PASSED" << timer() << endl;  else { cerr << "FAILED" << timer() << endl;
4fd800b3a8 2011-02-23        kinaba:  cerr << "\to: \"" << Expected << '\"' << endl << "\tx: \"" << Received << '\"' << endl; } }
4fd800b3a8 2011-02-23        kinaba: #define CASE(N) {cerr << "Test Case #" << N << "..." << flush; start_time=clock();
4fd800b3a8 2011-02-23        kinaba: #define END	 verify_case(_, TheAirTripDivOne().find(n, flights, time));}
4fd800b3a8 2011-02-23        kinaba: int main(){
4fd800b3a8 2011-02-23        kinaba: 
4fd800b3a8 2011-02-23        kinaba: CASE(0)
4fd800b3a8 2011-02-23        kinaba: 	int n = 3;
4fd800b3a8 2011-02-23        kinaba: 	string flights_[] = {"1,2,1,4,7 ", "2,3,9,1,10"};
4fd800b3a8 2011-02-23        kinaba: 	  vector <string> flights(flights_, flights_+sizeof(flights_)/sizeof(*flights_));
4fd800b3a8 2011-02-23        kinaba: 	int time = 20;
4fd800b3a8 2011-02-23        kinaba: 	int _ = 14;
4fd800b3a8 2011-02-23        kinaba: END
4fd800b3a8 2011-02-23        kinaba: CASE(1)
4fd800b3a8 2011-02-23        kinaba: 	int n = 3;
4fd800b3a8 2011-02-23        kinaba: 	string flights_[] = {"1,2,1,1,1 2,3,2,1,98"};
4fd800b3a8 2011-02-23        kinaba: 	  vector <string> flights(flights_, flights_+sizeof(flights_)/sizeof(*flights_));
4fd800b3a8 2011-02-23        kinaba: 	int time = 100;
4fd800b3a8 2011-02-23        kinaba: 	int _ = -1;
4fd800b3a8 2011-02-23        kinaba: END
4fd800b3a8 2011-02-23        kinaba: CASE(2)
4fd800b3a8 2011-02-23        kinaba: 	int n = 477;
4fd800b3a8 2011-02-23        kinaba: 	string flights_[] = {"47,74,1,1,1"};
4fd800b3a8 2011-02-23        kinaba: 	  vector <string> flights(flights_, flights_+sizeof(flights_)/sizeof(*flights_));
4fd800b3a8 2011-02-23        kinaba: 	int time = 20;
4fd800b3a8 2011-02-23        kinaba: 	int _ = -1;
4fd800b3a8 2011-02-23        kinaba: END
4fd800b3a8 2011-02-23        kinaba: CASE(3)
4fd800b3a8 2011-02-23        kinaba: 	int n = 7;
4fd800b3a8 2011-02-23        kinaba: 	string flights_[] = {"1,3,15,17,11 1,3,14,16,14 5,7,12,18,18 1,6,13,1",
4fd800b3a8 2011-02-23        kinaba:  "6,12 1,2,18,14,13 5,6,10,10,18 3,1,10,10,10 1,3",
4fd800b3a8 2011-02-23        kinaba:  ",17,16,10 2,3,16,18,16 6,1,15,12,10 2,1,15,18,1",
4fd800b3a8 2011-02-23        kinaba:  "0 4,7,10,16,15 6,3,10,14,10 1,6,19,19,15 1,4,12",
4fd800b3a8 2011-02-23        kinaba:  ",10,14 4,7,10,18,14 2,3,16,12,12 1,3,14,10,19 3",
4fd800b3a8 2011-02-23        kinaba:  ",7,17,10,12 2,1,14,12,16 4,3,19,11,12 1,6,10,18",
4fd800b3a8 2011-02-23        kinaba:  ",12 2,3,16,12,10 6,2,10,18,12 5,1,14,18,12 5,1,",
4fd800b3a8 2011-02-23        kinaba:  "18,10,10 3,2,19,15,10 7,4,16,19,14 6,3,16,12,10",
4fd800b3a8 2011-02-23        kinaba:  " 5,7,14,13,13 1,3,12,10,16 5,7,16,18,15 6,2,18,",
4fd800b3a8 2011-02-23        kinaba:  "12,14 3,2,10,18,16 4,2,18,18,14 1,5,10,18,16 2,",
4fd800b3a8 2011-02-23        kinaba:  "3,10,19,16 1,4,11,18,15 2,1,15,15,14 7,2,10,12,",
4fd800b3a8 2011-02-23        kinaba:  "10"};
4fd800b3a8 2011-02-23        kinaba: 	  vector <string> flights(flights_, flights_+sizeof(flights_)/sizeof(*flights_));
4fd800b3a8 2011-02-23        kinaba: 	int time = 74;
4fd800b3a8 2011-02-23        kinaba: 	int _ = 33;
4fd800b3a8 2011-02-23        kinaba: END
4fd800b3a8 2011-02-23        kinaba: CASE(4)
4fd800b3a8 2011-02-23        kinaba: 	int n = 7;
4fd800b3a8 2011-02-23        kinaba: 	string flights_[] = {"1,4,10,8,2 4,6,14,8,2 6,2,8,1",
4fd800b3a8 2011-02-23        kinaba:  "0,1 2,7,19,5,1 ",
4fd800b3a8 2011-02-23        kinaba:  "1,5,15,17,11 5,3,10,1",
4fd800b3a8 2011-02-23        kinaba:  "0,18 3,7,12,18,18"};
4fd800b3a8 2011-02-23        kinaba: 	  vector <string> flights(flights_, flights_+sizeof(flights_)/sizeof(*flights_));
4fd800b3a8 2011-02-23        kinaba: 	int time = 147;
4fd800b3a8 2011-02-23        kinaba: 	int _ = 35;
4fd800b3a8 2011-02-23        kinaba: END
4fd800b3a8 2011-02-23        kinaba: 	/*
4fd800b3a8 2011-02-23        kinaba: CASE(5)
4fd800b3a8 2011-02-23        kinaba: 	int n = ;
4fd800b3a8 2011-02-23        kinaba: 	string flights_[] = ;
4fd800b3a8 2011-02-23        kinaba: 	  vector <string> flights(flights_, flights_+sizeof(flights_)/sizeof(*flights_));
4fd800b3a8 2011-02-23        kinaba: 	int time = ;
4fd800b3a8 2011-02-23        kinaba: 	int _ = ;
4fd800b3a8 2011-02-23        kinaba: END
4fd800b3a8 2011-02-23        kinaba: CASE(6)
4fd800b3a8 2011-02-23        kinaba: 	int n = ;
4fd800b3a8 2011-02-23        kinaba: 	string flights_[] = ;
4fd800b3a8 2011-02-23        kinaba: 	  vector <string> flights(flights_, flights_+sizeof(flights_)/sizeof(*flights_));
4fd800b3a8 2011-02-23        kinaba: 	int time = ;
4fd800b3a8 2011-02-23        kinaba: 	int _ = ;
4fd800b3a8 2011-02-23        kinaba: END
4fd800b3a8 2011-02-23        kinaba: */
4fd800b3a8 2011-02-23        kinaba: }
4fd800b3a8 2011-02-23        kinaba: // END CUT HERE