File Annotation
Not logged in
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: typedef int             vert;
4fd800b3a8 2011-02-23        kinaba: typedef int             cost;
4fd800b3a8 2011-02-23        kinaba: typedef pair<cost,vert> edge;
4fd800b3a8 2011-02-23        kinaba: typedef vector<edge>    edges;
4fd800b3a8 2011-02-23        kinaba: typedef vector<edges>   graph;
4fd800b3a8 2011-02-23        kinaba: 
4fd800b3a8 2011-02-23        kinaba: static const cost INF   = 0x12345678; // large enough but INF+INF<2^31
4fd800b3a8 2011-02-23        kinaba: static const vert START = 0;
4fd800b3a8 2011-02-23        kinaba: static const vert GOAL  = 1;
4fd800b3a8 2011-02-23        kinaba: 
4fd800b3a8 2011-02-23        kinaba: class WarTransportation { public:
4fd800b3a8 2011-02-23        kinaba: 	int messenger(int n, vector <string> highways)
4fd800b3a8 2011-02-23        kinaba: 	{
4fd800b3a8 2011-02-23        kinaba: 		return solve( parse(n, highways) );
4fd800b3a8 2011-02-23        kinaba: 	}
4fd800b3a8 2011-02-23        kinaba: 
4fd800b3a8 2011-02-23        kinaba: 	graph parse(int n, vector <string> highways)
4fd800b3a8 2011-02-23        kinaba: 	{
4fd800b3a8 2011-02-23        kinaba: 		graph G(n);
4fd800b3a8 2011-02-23        kinaba: 
4fd800b3a8 2011-02-23        kinaba: 		string hi = accumulate(highways.begin(), highways.end(), string());
4fd800b3a8 2011-02-23        kinaba: 		for(int i=0; i<hi.size(); )
4fd800b3a8 2011-02-23        kinaba: 		{
4fd800b3a8 2011-02-23        kinaba: 			int k = hi.find(',', i);
4fd800b3a8 2011-02-23        kinaba: 			if( k == string::npos ) k = hi.size();
4fd800b3a8 2011-02-23        kinaba: 
4fd800b3a8 2011-02-23        kinaba: 			int a, b, c;
4fd800b3a8 2011-02-23        kinaba: 			stringstream(hi.substr(i,k-i)) >> a >> b >> c;
4fd800b3a8 2011-02-23        kinaba: 			G[a-1].push_back( edge(c,b-1) );
4fd800b3a8 2011-02-23        kinaba: 
4fd800b3a8 2011-02-23        kinaba: 			i = k+1;
4fd800b3a8 2011-02-23        kinaba: 		}
4fd800b3a8 2011-02-23        kinaba: 
4fd800b3a8 2011-02-23        kinaba: 		return G;
4fd800b3a8 2011-02-23        kinaba: 	}
4fd800b3a8 2011-02-23        kinaba: 
4fd800b3a8 2011-02-23        kinaba: 	int solve( const graph& G )
4fd800b3a8 2011-02-23        kinaba: 	{
4fd800b3a8 2011-02-23        kinaba: 		// Suppose you reached the city "v", and found there the most critical load is broken.
4fd800b3a8 2011-02-23        kinaba: 		// How long will it take a detour to the GOAL?  It's ukai[v]!
4fd800b3a8 2011-02-23        kinaba: 
4fd800b3a8 2011-02-23        kinaba: 		vector<cost> ukai;
4fd800b3a8 2011-02-23        kinaba: 		for(int v=0; v<G.size(); ++v)
4fd800b3a8 2011-02-23        kinaba: 			ukai.push_back( ukaiDist(G,v) );
4fd800b3a8 2011-02-23        kinaba: 
4fd800b3a8 2011-02-23        kinaba: 		// Compute the least T such that:
4fd800b3a8 2011-02-23        kinaba: 		//   we get to the GOAL, making the worst case time <= T?
4fd800b3a8 2011-02-23        kinaba: 
4fd800b3a8 2011-02-23        kinaba: 		cost L=0, R=99999999;
4fd800b3a8 2011-02-23        kinaba: 		if( !reachable(G, ukai, R) ) return -1;
4fd800b3a8 2011-02-23        kinaba: 		if(  reachable(G, ukai, L) ) return 0;
4fd800b3a8 2011-02-23        kinaba: 
4fd800b3a8 2011-02-23        kinaba: 		// We can when T=R, and cannot T=L.
4fd800b3a8 2011-02-23        kinaba: 		// That is, T in (L, R]. Now let's binary-search!
4fd800b3a8 2011-02-23        kinaba: 
4fd800b3a8 2011-02-23        kinaba: 		while( R-L>1 )
4fd800b3a8 2011-02-23        kinaba: 			(reachable(G, ukai, (L+R)/2) ? R : L) = (L+R)/2;
4fd800b3a8 2011-02-23        kinaba: 		return R;
4fd800b3a8 2011-02-23        kinaba: 	}
4fd800b3a8 2011-02-23        kinaba: 
4fd800b3a8 2011-02-23        kinaba: 	cost ukaiDist( const graph& G, vert v )
4fd800b3a8 2011-02-23        kinaba: 	{
4fd800b3a8 2011-02-23        kinaba: 		if( v == GOAL )        return 0;
4fd800b3a8 2011-02-23        kinaba: 		if( G[v].size() == 0 ) return INF;
4fd800b3a8 2011-02-23        kinaba: 
4fd800b3a8 2011-02-23        kinaba: 		cost worst = 0;
4fd800b3a8 2011-02-23        kinaba: 		for(int f=0; f<G[v].size(); ++f) // f : broken road
4fd800b3a8 2011-02-23        kinaba: 		{
4fd800b3a8 2011-02-23        kinaba: 			priority_queue< edge, vector<edge>, greater<edge> > Q;
4fd800b3a8 2011-02-23        kinaba: 			set<vert> V;
4fd800b3a8 2011-02-23        kinaba: 			V.insert(v);
4fd800b3a8 2011-02-23        kinaba: 			for(int i=0; i<G[v].size(); ++i) // push all loads from v, except f
4fd800b3a8 2011-02-23        kinaba: 				if( i != f )
4fd800b3a8 2011-02-23        kinaba: 					Q.push( G[v][i] );
4fd800b3a8 2011-02-23        kinaba: 			worst = max( worst, dijkstra(G,Q,V) ); // start dijkstraing
4fd800b3a8 2011-02-23        kinaba: 		}
4fd800b3a8 2011-02-23        kinaba: 		return worst;
4fd800b3a8 2011-02-23        kinaba: 	}
4fd800b3a8 2011-02-23        kinaba: 
4fd800b3a8 2011-02-23        kinaba: 
4fd800b3a8 2011-02-23        kinaba: 	bool reachable( const graph& G, const vector<cost>& ukai, cost ukaiLimit )
4fd800b3a8 2011-02-23        kinaba: 	{
4fd800b3a8 2011-02-23        kinaba: 		priority_queue< edge, vector<edge>, greater<edge> > Q;
4fd800b3a8 2011-02-23        kinaba: 		set<vert> V;
4fd800b3a8 2011-02-23        kinaba: 		Q.push( edge(0,START) );
4fd800b3a8 2011-02-23        kinaba: 		return dijkstra(G, Q, V, ukai, ukaiLimit) != INF;
4fd800b3a8 2011-02-23        kinaba: 	}
4fd800b3a8 2011-02-23        kinaba: 
4fd800b3a8 2011-02-23        kinaba: 	cost dijkstra( const graph& G,
4fd800b3a8 2011-02-23        kinaba: 		priority_queue< edge, vector<edge>, greater<edge> >& Q, set<vert>& V,
4fd800b3a8 2011-02-23        kinaba: 		const vector<cost>& ukai=vector<cost>(), cost ukaiLimit=-1
4fd800b3a8 2011-02-23        kinaba: 	) {
4fd800b3a8 2011-02-23        kinaba: 		while( !Q.empty() )
4fd800b3a8 2011-02-23        kinaba: 		{
4fd800b3a8 2011-02-23        kinaba: 			// pop
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: 
4fd800b3a8 2011-02-23        kinaba: 			// check
4fd800b3a8 2011-02-23        kinaba: 			if( V.count(v) || (ukaiLimit>=0 && c+ukai[v]>ukaiLimit) )
4fd800b3a8 2011-02-23        kinaba: 				continue;
4fd800b3a8 2011-02-23        kinaba: 			if( v == GOAL )
4fd800b3a8 2011-02-23        kinaba: 				 return c;
4fd800b3a8 2011-02-23        kinaba: 			V.insert(v);
4fd800b3a8 2011-02-23        kinaba: 
4fd800b3a8 2011-02-23        kinaba: 			// next
4fd800b3a8 2011-02-23        kinaba: 			for(int i=0; i<G[v].size(); ++i)
4fd800b3a8 2011-02-23        kinaba: 				if( !V.count(G[v][i].second) )
4fd800b3a8 2011-02-23        kinaba: 					Q.push( edge(c+G[v][i].first, G[v][i].second) );
4fd800b3a8 2011-02-23        kinaba: 		}
4fd800b3a8 2011-02-23        kinaba: 		return INF;
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(_, WarTransportation().messenger(n, highways));}
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 highways_[] = {"1 2 1,1 3 2,3 2 3"};
4fd800b3a8 2011-02-23        kinaba: 	  vector <string> highways(highways_, highways_+sizeof(highways_)/sizeof(*highways_));
4fd800b3a8 2011-02-23        kinaba: 	int _ = 5;
4fd800b3a8 2011-02-23        kinaba: END
4fd800b3a8 2011-02-23        kinaba: CASE(1)
4fd800b3a8 2011-02-23        kinaba: 	int n = 8;
4fd800b3a8 2011-02-23        kinaba: 	string highways_[] = {"1 3 1,1 4 1,3 5 1,4 5 1,5 6 1,6 7 1,6 8 1,7 2 1,",
4fd800b3a8 2011-02-23        kinaba:  "8 2 1"};
4fd800b3a8 2011-02-23        kinaba: 	  vector <string> highways(highways_, highways_+sizeof(highways_)/sizeof(*highways_));
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 = 4;
4fd800b3a8 2011-02-23        kinaba: 	string highways_[] = {"1 3 1,1 3 2,3 2 1,1 4 1,4 2 1"};
4fd800b3a8 2011-02-23        kinaba: 	  vector <string> highways(highways_, highways_+sizeof(highways_)/sizeof(*highways_));
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 = 4;
4fd800b3a8 2011-02-23        kinaba: 	string highways_[] = {"1 3 1,3 2 1,1 4 1,4 2 1,3 4 1"};
4fd800b3a8 2011-02-23        kinaba: 	  vector <string> highways(highways_, highways_+sizeof(highways_)/sizeof(*highways_));
4fd800b3a8 2011-02-23        kinaba: 	int _ = 3;
4fd800b3a8 2011-02-23        kinaba: END
4fd800b3a8 2011-02-23        kinaba: CASE(4)
4fd800b3a8 2011-02-23        kinaba: 	int n = 20;
4fd800b3a8 2011-02-23        kinaba: 	string highways_[] = {"1 13 3,13 4 7,4 3 4,3 10 8,10 18 9,18 12 6,12 2 3,",
4fd800b3a8 2011-02-23        kinaba:  "1 17 6,17 13 6,13 9 4,9 10 8,10 7 2,7 5 5,5 19 9,1",
4fd800b3a8 2011-02-23        kinaba:  "9 14 6,14 16 9,16 18 7,18 15 5,15 20 3,20 12 9,12 ",
4fd800b3a8 2011-02-23        kinaba:  "8 4,8 11 3,11 4 1,4 3 7,3 2 3,20 10 2,1 18 2,16 19",
4fd800b3a8 2011-02-23        kinaba:  " 9,4 15 9,13 15 6"};
4fd800b3a8 2011-02-23        kinaba: 	  vector <string> highways(highways_, highways_+sizeof(highways_)/sizeof(*highways_));
4fd800b3a8 2011-02-23        kinaba: 	int _ = 23;
4fd800b3a8 2011-02-23        kinaba: END
4fd800b3a8 2011-02-23        kinaba: CASE(5)
4fd800b3a8 2011-02-23        kinaba: 	int n = 30;
4fd800b3a8 2011-02-23        kinaba: 	string highways_[] = {
4fd800b3a8 2011-02-23        kinaba: 		"11 22 752,9 28 573,8 20 549,2 29 96,12 25 835,11 2", "3 443,28 20 59,5 16 223,29 24 382,14 6 436,5 21 47", "7,28 1 290,20 23 567,6 26 347,14 8 436,23 7 585,22", " 14 829,19 8 897,18 7 161,29 22 446,6 3 47,6 11 11", "9,23 13 357,15 2 539,30 27 246,20 26 364,11 13 518", ",20 29 360,10 9 140,9 19 178,24 5 75,4 9 465,22 4 ", "271,21 25 632,25 16 705,23 19 777,15 11 668,25 6 9", "11,26 21 940,27 12 114,23 29 775,15 22 907,10 15 1", "86,25 21 727,26 7 324,15 21 251,20 7 369,29 9 5,5 ", "4 780,10 23 774,13 15 65,2 8 938,9 3 150,6 9 109,4", " 22 649,24 13 274,14 3 403,12 19 66,3 13 798,7 20 ", "912,24 14 751,25 27 575,14 20 580,2 5 110,24 7 215", ",1 5 194,3 2 786,2 19 716,22 24 331,9 21 375,15 9 ", "397,18 27 753,24 23 181,17 27 386,12 30 313,18 25 ", "155,19 24 162,11 7 533,13 2 307,20 21 100,14 24 52", "6,29 8 505,28 8 776,5 27 949,16 14 43,16 30 84,10 ", "1 323,12 18 590,8 15 357,12 6 185,20 8 328,26 4 83", ",5 10 67,1 11 582,9 23 610,16 1 246,6 4 679,22 21 ", "149,17 10 321,29 27 560,20 19 771,11 30 506,6 25 1", "83,1 23 948,23 17 125,26 5 912,15 23 470,30 10 293", ",4 18 313,11 19 261,16 29 259,19 5 408,18 12 960,2", "4 3 743,17 3 4,30 17 347,11 2 648,16 8 868,12 10 6", "50,21 14 425,5 28 947,10 13 578,14 15 681,5 2 656,", "16 12 447,26 27 915,16 10 477,8 25 994,20 10 582,9", " 7 420,10 26 389,20 22 360,26 10 321,28 19 922,23 ", "20 393,13 14 447,29 15 33,30 1 811,2 28 597,13 8 5", "9,18 29 437,23 2 101,30 12 999,1 27 701,19 28 534,", "23 21 518,3 11 589,18 14 662,5 14 455,16 15 230,2 ", "17 633,19 13 242,10 18 404,10 4 731,15 6 221,25 15", " 747,3 23 465,24 9 569,12 11 645,5 24 748,23 26 44", "4,30 21 451,29 17 141,25 3 292,26 6 400,18 8 497,2", "4 19 901,17 5 49,21 12 141,30 18 7,20 18 271,13 3 ", "17,29 4 952,2 13 903,1 24 558,25 1 125,14 13 914,1", "4 12 385,1 3 40,30 8 704,18 5 901,19 10 822,22 27 ", "938,5 18 808,5 29 1,10 8 791,2 7 920,12 5 359,5 9 ", "744,1 25 819,6 30 262,24 6 7,12 7 870,17 25 932,28", " 18 771,23 16 699,26 24 834,27 20 824,30 23 95,22 ", "5 553,26 29 150,25 4 70,4 20 501,9 16 291,2 30 40,", "19 18 602,19 3 108,29 11 827,19 22 702,26 11 238,2", "8 22 392,22 10 496,13 25 160,12 24 700,22 29 654,9", " 2 701,28 7 946,21 5 223,7 22 902,12 15 43,21 8 67", "8,28 27 946,7 15 603,15 8 114,25 10 234,19 4 128,2", "4 8 990,11 12 554,23 9 646,10 24 755,8 16 857,23 1", " 806,15 13 929,21 11 601,19 30 245,17 21 474,27 25", " 638,11 21 411,4 26 895,13 24 599,12 13 226,30 22 ", "104,30 24 53,29 10 69,29 30 263,28 6 349,6 16 982,", "4 6 273,1 30 533,29 21 443,7 3 867,17 11 756,1 7 6", "87,29 2 799,5 22 42,16 20 708,25 11 476,23 8 186,2", "3 3 820,23 18 226,21 9 429,17 26 201,25 26 79,12 2", " 671,23 14 698,10 30 92,3 25 380,14 30 420"};
4fd800b3a8 2011-02-23        kinaba: 	  vector <string> highways(highways_, highways_+sizeof(highways_)/sizeof(*highways_));
4fd800b3a8 2011-02-23        kinaba: 	int _ = 799;
4fd800b3a8 2011-02-23        kinaba: END
4fd800b3a8 2011-02-23        kinaba: /*
4fd800b3a8 2011-02-23        kinaba: CASE(6)
4fd800b3a8 2011-02-23        kinaba: 	int n = ;
4fd800b3a8 2011-02-23        kinaba: 	string highways_[] = ;
4fd800b3a8 2011-02-23        kinaba: 	  vector <string> highways(highways_, highways_+sizeof(highways_)/sizeof(*highways_));
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