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