Artifact Content
Not logged in

Artifact 5d5ec3acb844c5c957d6ec210d5d8a3bd21fb7d4


#include <iostream>
#include <sstream>
#include <iomanip>
#include <vector>
#include <string>
#include <map>
#include <set>
#include <algorithm>
#include <numeric>
#include <iterator>
#include <functional>
#include <complex>
#include <queue>
#include <stack>
#include <cmath>
#include <cassert>
#include <cstring>
using namespace std;
typedef long long LL;
typedef complex<double> CMP;

class TheAirTripDivOne { public:
	struct edge {
		int to;
		LL F, T, P;
	};
	int find(int n, vector <string> flights, int time) 
	{
		vector< vector<edge> > e(n);
		{
			string input = accumulate(flights.begin(), flights.end(), string(""));
			stringstream sin(input);
			for(string line; sin>>line;) {
				stringstream sin(line);
				int a,b; LL f,t,p; char _;
				sin >> a >> _ >> b >> _ >> f >> _ >> t >> _ >> p;
				edge eg = {b-1,f,t,p};
				e[a-1].push_back(eg);
			}
		}

		int lf=0, ri=1000000001;
		while( ri-lf>1 )
		{
			int c = (lf+ri)/2;
			(ok(n,e,c,time) ? lf : ri) = c;
		}
		return lf ? lf : -1;
	}
	bool ok(int n, vector< vector<edge> >& e, LL transfer, LL TL)
	{
		typedef int vert;
		typedef LL cost;
		typedef pair<cost,int> cedge;
		priority_queue<cedge, vector<cedge>, greater<cedge> > Q;
		set<vert> V;
		Q.push( cedge(0,0) );
		while( !Q.empty() )
		{
			cost c = Q.top().first;
			vert v = Q.top().second;
			Q.pop();
			if( V.count(v) )
				continue;
			if( v == n-1 )
				return true;
			V.insert(v);
			vector<edge>& ne = e[v];
			for(int i=0; i<ne.size(); ++i)
			{
				vert u = ne[i].to;
				LL F=ne[i].F, T=ne[i].T, P=ne[i].P;
				LL t = nextTime(c, F, P, v==0 ? 0 : transfer);
//				cerr<<c<<" "<<F<<" "<<P<<" "<<transfer<<" !! "<<t<<endl;
				if( !V.count(u) && t+T<=TL )
					Q.push( cedge(t+T, u) );
			}
		}
		return false;
	}

	LL nextTime(LL cur, LL F, LL P, LL transfer)
	{
		cur += transfer;
		if( cur <= F )
			return F;
		return (cur-F)%P==0 ? cur : ((cur-F)/P+1)*P+F;
	}
};

// BEGIN CUT HERE
#include <ctime>
double start_time; string timer()
 { ostringstream os; os << " (" << int((clock()-start_time)/CLOCKS_PER_SEC*1000) << " msec)"; return os.str(); }
template<typename T> ostream& operator<<(ostream& os, const vector<T>& v)
 { os << "{ ";
   for(typename vector<T>::const_iterator it=v.begin(); it!=v.end(); ++it)
   os << '\"' << *it << '\"' << (it+1==v.end() ? "" : ", "); os << " }"; return os; }
void verify_case(const int& Expected, const int& Received) {
 bool ok = (Expected == Received);
 if(ok) cerr << "PASSED" << timer() << endl;  else { cerr << "FAILED" << timer() << endl;
 cerr << "\to: \"" << Expected << '\"' << endl << "\tx: \"" << Received << '\"' << endl; } }
#define CASE(N) {cerr << "Test Case #" << N << "..." << flush; start_time=clock();
#define END	 verify_case(_, TheAirTripDivOne().find(n, flights, time));}
int main(){

CASE(0)
	int n = 3; 
	string flights_[] = {"1,2,1,4,7 ", "2,3,9,1,10"};
	  vector <string> flights(flights_, flights_+sizeof(flights_)/sizeof(*flights_)); 
	int time = 20; 
	int _ = 14; 
END
CASE(1)
	int n = 3; 
	string flights_[] = {"1,2,1,1,1 2,3,2,1,98"};
	  vector <string> flights(flights_, flights_+sizeof(flights_)/sizeof(*flights_)); 
	int time = 100; 
	int _ = -1; 
END
CASE(2)
	int n = 477; 
	string flights_[] = {"47,74,1,1,1"};
	  vector <string> flights(flights_, flights_+sizeof(flights_)/sizeof(*flights_)); 
	int time = 20; 
	int _ = -1; 
END
CASE(3)
	int n = 7; 
	string flights_[] = {"1,3,15,17,11 1,3,14,16,14 5,7,12,18,18 1,6,13,1", 
 "6,12 1,2,18,14,13 5,6,10,10,18 3,1,10,10,10 1,3",
 ",17,16,10 2,3,16,18,16 6,1,15,12,10 2,1,15,18,1",
 "0 4,7,10,16,15 6,3,10,14,10 1,6,19,19,15 1,4,12",
 ",10,14 4,7,10,18,14 2,3,16,12,12 1,3,14,10,19 3",
 ",7,17,10,12 2,1,14,12,16 4,3,19,11,12 1,6,10,18",
 ",12 2,3,16,12,10 6,2,10,18,12 5,1,14,18,12 5,1,",
 "18,10,10 3,2,19,15,10 7,4,16,19,14 6,3,16,12,10",
 " 5,7,14,13,13 1,3,12,10,16 5,7,16,18,15 6,2,18,",
 "12,14 3,2,10,18,16 4,2,18,18,14 1,5,10,18,16 2,",
 "3,10,19,16 1,4,11,18,15 2,1,15,15,14 7,2,10,12,",
 "10"};
	  vector <string> flights(flights_, flights_+sizeof(flights_)/sizeof(*flights_)); 
	int time = 74; 
	int _ = 33; 
END
CASE(4)
	int n = 7; 
	string flights_[] = {"1,4,10,8,2 4,6,14,8,2 6,2,8,1",
 "0,1 2,7,19,5,1 ",
 "1,5,15,17,11 5,3,10,1",
 "0,18 3,7,12,18,18"};
	  vector <string> flights(flights_, flights_+sizeof(flights_)/sizeof(*flights_)); 
	int time = 147; 
	int _ = 35; 
END
	/*
CASE(5)
	int n = ; 
	string flights_[] = ;
	  vector <string> flights(flights_, flights_+sizeof(flights_)/sizeof(*flights_)); 
	int time = ; 
	int _ = ; 
END
CASE(6)
	int n = ; 
	string flights_[] = ;
	  vector <string> flights(flights_, flights_+sizeof(flights_)/sizeof(*flights_)); 
	int time = ; 
	int _ = ; 
END
*/
}
// END CUT HERE