d6047a481e 2014-07-05 kinaba: #include <iostream> d6047a481e 2014-07-05 kinaba: #include <sstream> d6047a481e 2014-07-05 kinaba: #include <iomanip> d6047a481e 2014-07-05 kinaba: #include <vector> d6047a481e 2014-07-05 kinaba: #include <string> d6047a481e 2014-07-05 kinaba: #include <map> d6047a481e 2014-07-05 kinaba: #include <set> d6047a481e 2014-07-05 kinaba: #include <algorithm> d6047a481e 2014-07-05 kinaba: #include <numeric> d6047a481e 2014-07-05 kinaba: #include <iterator> d6047a481e 2014-07-05 kinaba: #include <functional> d6047a481e 2014-07-05 kinaba: #include <complex> d6047a481e 2014-07-05 kinaba: #include <queue> d6047a481e 2014-07-05 kinaba: #include <stack> d6047a481e 2014-07-05 kinaba: #include <cmath> d6047a481e 2014-07-05 kinaba: #include <cassert> d6047a481e 2014-07-05 kinaba: #include <tuple> d6047a481e 2014-07-05 kinaba: using namespace std; d6047a481e 2014-07-05 kinaba: typedef long long LL; d6047a481e 2014-07-05 kinaba: typedef complex<double> CMP; d6047a481e 2014-07-05 kinaba: static const LL INF = 0x1fffffffffffffffLL; d6047a481e 2014-07-05 kinaba: d6047a481e 2014-07-05 kinaba: class NegativeGraphDiv1 { public: d6047a481e 2014-07-05 kinaba: long long findMin(int N, vector <int> from, vector <int> to, vector <int> weight, int charges) d6047a481e 2014-07-05 kinaba: { d6047a481e 2014-07-05 kinaba: // base graph d6047a481e 2014-07-05 kinaba: vector<vector<LL>> g(N, vector<LL>(N, INF)); d6047a481e 2014-07-05 kinaba: vector<vector<LL>> g_neg(N, vector<LL>(N, INF)); d6047a481e 2014-07-05 kinaba: for(int i=0; i<N; ++i) d6047a481e 2014-07-05 kinaba: g[i][i] = 0; d6047a481e 2014-07-05 kinaba: for(int i=0; i<from.size(); ++i) { d6047a481e 2014-07-05 kinaba: int f = from[i]-1; d6047a481e 2014-07-05 kinaba: int t = to[i]-1; d6047a481e 2014-07-05 kinaba: LL w = weight[i]; d6047a481e 2014-07-05 kinaba: g[f][t] = min(g[f][t], w); d6047a481e 2014-07-05 kinaba: g_neg[f][t] = min(g_neg[f][t], -w); d6047a481e 2014-07-05 kinaba: } d6047a481e 2014-07-05 kinaba: d6047a481e 2014-07-05 kinaba: int CMAX = N*2; d6047a481e 2014-07-05 kinaba: d6047a481e 2014-07-05 kinaba: // 0-magic d6047a481e 2014-07-05 kinaba: vector<vector<vector<LL>>> d(CMAX+1, g); d6047a481e 2014-07-05 kinaba: for(int k=0; k<N; ++k) d6047a481e 2014-07-05 kinaba: for(int i=0; i<N; ++i) d6047a481e 2014-07-05 kinaba: for(int j=0; j<N; ++j) d6047a481e 2014-07-05 kinaba: d[0][i][j] = min(d[0][i][j], d[0][i][k]+d[0][k][j]); d6047a481e 2014-07-05 kinaba: // 1-magic d6047a481e 2014-07-05 kinaba: for(int a=0; a<N; ++a) d6047a481e 2014-07-05 kinaba: for(int b=0; b<N; ++b) d6047a481e 2014-07-05 kinaba: for(int c=0; c<N; ++c) d6047a481e 2014-07-05 kinaba: for(int z=0; z<N; ++z) d6047a481e 2014-07-05 kinaba: d[1][a][z] = min(d[1][a][z], d[0][a][b] + g_neg[b][c] + d[0][c][z]); d6047a481e 2014-07-05 kinaba: d6047a481e 2014-07-05 kinaba: // C-magic d6047a481e 2014-07-05 kinaba: for(int C=1; C<=CMAX; ++C) { d6047a481e 2014-07-05 kinaba: for(int a=0; a<N; ++a) d6047a481e 2014-07-05 kinaba: for(int b=0; b<N; ++b) d6047a481e 2014-07-05 kinaba: for(int z=0; z<N; ++z) d6047a481e 2014-07-05 kinaba: d[C][a][z] = min(d[C][a][z], d[1][a][b] + d[C-1][b][z]); d6047a481e 2014-07-05 kinaba: } d6047a481e 2014-07-05 kinaba: d6047a481e 2014-07-05 kinaba: // go,cycle,go d6047a481e 2014-07-05 kinaba: LL best = INF; d6047a481e 2014-07-05 kinaba: for(int S=0; S<=min(CMAX,charges); ++S) d6047a481e 2014-07-05 kinaba: best = min(best, d[S][0][N-1]); d6047a481e 2014-07-05 kinaba: for(int S=0; S<=N; ++S) d6047a481e 2014-07-05 kinaba: for(int M=1; M<=N; ++M) d6047a481e 2014-07-05 kinaba: for(int E=0; E<=CMAX; ++E) if(S+E<=charges) d6047a481e 2014-07-05 kinaba: for(int x=0; x<N; ++x) d6047a481e 2014-07-05 kinaba: best = min(best, d[S][0][x] + d[M][x][x]*((charges-S-E)/M) + d[E][x][N-1]); d6047a481e 2014-07-05 kinaba: return best; d6047a481e 2014-07-05 kinaba: } d6047a481e 2014-07-05 kinaba: }; d6047a481e 2014-07-05 kinaba: d6047a481e 2014-07-05 kinaba: // BEGIN CUT HERE d6047a481e 2014-07-05 kinaba: #include <ctime> d6047a481e 2014-07-05 kinaba: double start_time; string timer() d6047a481e 2014-07-05 kinaba: { ostringstream os; os << " (" << int((clock()-start_time)/CLOCKS_PER_SEC*1000) << " msec)"; return os.str(); } d6047a481e 2014-07-05 kinaba: template<typename T> ostream& operator<<(ostream& os, const vector<T>& v) d6047a481e 2014-07-05 kinaba: { os << "{ "; d6047a481e 2014-07-05 kinaba: for(typename vector<T>::const_iterator it=v.begin(); it!=v.end(); ++it) d6047a481e 2014-07-05 kinaba: os << '\"' << *it << '\"' << (it+1==v.end() ? "" : ", "); os << " }"; return os; } d6047a481e 2014-07-05 kinaba: void verify_case(const long long& Expected, const long long& Received) { d6047a481e 2014-07-05 kinaba: bool ok = (Expected == Received); d6047a481e 2014-07-05 kinaba: if(ok) cerr << "PASSED" << timer() << endl; else { cerr << "FAILED" << timer() << endl; d6047a481e 2014-07-05 kinaba: cerr << "\to: \"" << Expected << '\"' << endl << "\tx: \"" << Received << '\"' << endl; } } d6047a481e 2014-07-05 kinaba: #define CASE(N) {cerr << "Test Case #" << N << "..." << flush; start_time=clock(); d6047a481e 2014-07-05 kinaba: #define END verify_case(_, NegativeGraphDiv1().findMin(N, from, to, weight, charges));} d6047a481e 2014-07-05 kinaba: int main(){ d6047a481e 2014-07-05 kinaba: d6047a481e 2014-07-05 kinaba: CASE(0) d6047a481e 2014-07-05 kinaba: int N = 3; d6047a481e 2014-07-05 kinaba: int from_[] = {1,1,2,2,3,3}; d6047a481e 2014-07-05 kinaba: vector <int> from(from_, from_+sizeof(from_)/sizeof(*from_)); d6047a481e 2014-07-05 kinaba: int to_[] = {2,3,1,3,1,2}; d6047a481e 2014-07-05 kinaba: vector <int> to(to_, to_+sizeof(to_)/sizeof(*to_)); d6047a481e 2014-07-05 kinaba: int weight_[] = {1,5,1,10,1,1}; d6047a481e 2014-07-05 kinaba: vector <int> weight(weight_, weight_+sizeof(weight_)/sizeof(*weight_)); d6047a481e 2014-07-05 kinaba: int charges = 1; d6047a481e 2014-07-05 kinaba: long long _ = -9LL; d6047a481e 2014-07-05 kinaba: END d6047a481e 2014-07-05 kinaba: CASE(1) d6047a481e 2014-07-05 kinaba: int N = 1; d6047a481e 2014-07-05 kinaba: int from_[] = {1}; d6047a481e 2014-07-05 kinaba: vector <int> from(from_, from_+sizeof(from_)/sizeof(*from_)); d6047a481e 2014-07-05 kinaba: int to_[] = {1}; d6047a481e 2014-07-05 kinaba: vector <int> to(to_, to_+sizeof(to_)/sizeof(*to_)); d6047a481e 2014-07-05 kinaba: int weight_[] = {100}; d6047a481e 2014-07-05 kinaba: vector <int> weight(weight_, weight_+sizeof(weight_)/sizeof(*weight_)); d6047a481e 2014-07-05 kinaba: int charges = 100000; d6047a481e 2014-07-05 kinaba: long long _ = -10000000LL; d6047a481e 2014-07-05 kinaba: END d6047a481e 2014-07-05 kinaba: CASE(2) d6047a481e 2014-07-05 kinaba: int N = 2; d6047a481e 2014-07-05 kinaba: int from_[] = {1,1,2}; d6047a481e 2014-07-05 kinaba: vector <int> from(from_, from_+sizeof(from_)/sizeof(*from_)); d6047a481e 2014-07-05 kinaba: int to_[] = {2,2,1}; d6047a481e 2014-07-05 kinaba: vector <int> to(to_, to_+sizeof(to_)/sizeof(*to_)); d6047a481e 2014-07-05 kinaba: int weight_[] = {6,1,4}; d6047a481e 2014-07-05 kinaba: vector <int> weight(weight_, weight_+sizeof(weight_)/sizeof(*weight_)); d6047a481e 2014-07-05 kinaba: int charges = 2; d6047a481e 2014-07-05 kinaba: long long _ = -9LL; d6047a481e 2014-07-05 kinaba: END d6047a481e 2014-07-05 kinaba: CASE(3) d6047a481e 2014-07-05 kinaba: int N = 2; d6047a481e 2014-07-05 kinaba: int from_[] = {1}; d6047a481e 2014-07-05 kinaba: vector <int> from(from_, from_+sizeof(from_)/sizeof(*from_)); d6047a481e 2014-07-05 kinaba: int to_[] = {2}; d6047a481e 2014-07-05 kinaba: vector <int> to(to_, to_+sizeof(to_)/sizeof(*to_)); d6047a481e 2014-07-05 kinaba: int weight_[] = {98765}; d6047a481e 2014-07-05 kinaba: vector <int> weight(weight_, weight_+sizeof(weight_)/sizeof(*weight_)); d6047a481e 2014-07-05 kinaba: int charges = 1000000000; d6047a481e 2014-07-05 kinaba: long long _ = -98765LL; d6047a481e 2014-07-05 kinaba: END d6047a481e 2014-07-05 kinaba: CASE(4) d6047a481e 2014-07-05 kinaba: int N = 40; d6047a481e 2014-07-05 kinaba: int from_[] = {21,2,36,21,32,1,34,1,40,38,19,10,39,40,31,29,22,18,24,8,25,1,12,31,1,34,16,13,39,39,26,30,4,28,8,9,27,13,6,16,7,11,7,38,30,20,22,29,19,5,22,13,12,7, d6047a481e 2014-07-05 kinaba: 33,5,10,31,10,39,18,18,3,19,17,17,34,9,7,17,21,13,12,16,36,39,9,7,3,5,26,16,32,4,26,12,27,24,19,1,19,17,9,22,16,12,31,37,32,9,31,8,2,39,18,26,32,12, d6047a481e 2014-07-05 kinaba: 28,11,32,34,2,12,12,33,27,24,5,5,40,34,4,8,10,17,39,30,26,24,10,37,23,40,38,17,4,28,33,31,28,19,36,5,24,17,11,19,4,40,20,16,11,10,9,22,23,23,8,30,10, d6047a481e 2014-07-05 kinaba: 23,16,21,10,18,8,28,15,20,38,5,22,4,29,32,13,13,15,24,28,27,11,24,24,23,40,34,20,28,18,26,34,21,13,11,33,28,8,5,9,31,1,32,7,22,12,8,12,8,12,31,35,33, d6047a481e 2014-07-05 kinaba: 27,18,6,22,38,9,40,35,15,16,30,4,3,29,2,34,40,3,12,20,29,14,2,3,8,37,12,28,25,7,22,33,4,15,5,14,26,22,16,33,12,11,14,11,5,25,30,21,20,30,25,30,28,37, d6047a481e 2014-07-05 kinaba: 23,31,30,3,15,5,25,14,8,13,12,4,18,9,20,17,11,21,5,25,15,9,40,26,28,36,1,10,33,34,5,3,21,32,15,30,33,32,31,19,12,2,16,13,15,4,33,33,26,6,7,36,20,14,7, d6047a481e 2014-07-05 kinaba: 39,17,33,4,5,22,21,13,29,38,34,6,24,18,29,4,20,33,16,14,30,20,20,7,21,13,5,20,1,8,18,9,12,24,10,22,33,40,28,30,23,7,36,27,38,36,15,3,36,8,20,27,12,5, d6047a481e 2014-07-05 kinaba: 33,40,7,25,20,13,36,30,13,9,3,15,38,33,27,36,4,9,18,39,7,12,30,17,2,21,17,11,26,14,29,26,31,15,13,12,19,35,11,25,19,15,34,9,12,17,37,22,22,16,10,13, d6047a481e 2014-07-05 kinaba: 17,12,12,32,1,40,10,34,29,39,7,17,3}; d6047a481e 2014-07-05 kinaba: vector <int> from(from_, from_+sizeof(from_)/sizeof(*from_)); d6047a481e 2014-07-05 kinaba: int to_[] = {27,37,32,14,19,25,4,14,40,9,36,23,21,25,39,13,4,30,11,32,22,12,29,40,35,32,4,15,25,8,17,18,17,19,34,1,16,16,26,28,2,28,21,16,6,3,12,39,24,31,3,25,26, d6047a481e 2014-07-05 kinaba: 30,9,35,29,20,4,21,25,15,32,27,24,13,3,10,21,40,12,39,4,10,2,39,28,23,21,19,21,11,32,20,36,7,11,21,16,29,17,24,18,32,17,38,23,35,1,19,28,20,31,37,16, d6047a481e 2014-07-05 kinaba: 20,7,31,3,7,36,15,36,10,6,37,26,39,39,26,31,8,36,26,10,21,24,33,13,29,31,10,12,20,31,39,35,29,39,30,34,26,15,30,4,36,16,38,2,31,22,18,17,12,21,4,11, d6047a481e 2014-07-05 kinaba: 32,3,27,14,22,16,37,40,18,25,28,20,27,27,30,11,19,16,18,25,4,21,14,14,13,22,34,25,9,31,27,14,32,23,21,3,1,24,15,30,35,1,24,37,7,28,8,21,40,6,29,36,37, d6047a481e 2014-07-05 kinaba: 21,8,17,20,20,28,22,22,13,29,34,20,26,11,10,8,33,10,37,11,16,5,9,18,39,1,8,4,5,2,20,30,4,23,30,23,19,25,30,37,40,31,31,33,33,8,36,40,15,11,31,37,5,40, d6047a481e 2014-07-05 kinaba: 2,11,19,32,1,32,27,7,23,9,13,18,12,36,11,32,34,38,35,15,6,36,32,28,6,40,2,33,2,6,7,27,40,30,40,12,39,13,1,22,17,36,1,4,34,25,25,6,20,25,30,4,24,35,7,5, d6047a481e 2014-07-05 kinaba: 29,20,28,37,1,30,6,5,5,1,10,40,13,14,21,32,19,25,37,21,28,34,28,29,27,24,33,35,12,25,3,4,12,31,12,7,28,27,10,35,35,18,6,5,16,24,39,26,15,29,13,5,14,36, d6047a481e 2014-07-05 kinaba: 35,14,2,39,22,21,2,2,19,38,15,25,10,13,2,39,31,13,5,39,11,33,4,18,18,38,19,39,39,32,23,34,30,21,30,16,36,22,25,14,13,16,10,8,27,29,40,1,29,4,20,25,32, d6047a481e 2014-07-05 kinaba: 21,40,1,10,2,17,5,8,5,31,18,18,25,13,3}; d6047a481e 2014-07-05 kinaba: vector <int> to(to_, to_+sizeof(to_)/sizeof(*to_)); d6047a481e 2014-07-05 kinaba: int weight_[] = {93486,55539,34680,56705,10415,99106,26365,51838,20794,93178,33943,80260,60780,2405,78346,71929,24723,37614,62649,83486,32073,83866,88345,83213,28266, d6047a481e 2014-07-05 kinaba: 12730,27623,25353,89948,55002,36720,87151,39759,66091,3690,83881,82635,69084,54138,65876,54205,10236,90478,37230,22337,8209,14258,18375,5268,21824, d6047a481e 2014-07-05 kinaba: 76819,4094,63971,1454,21318,44848,92540,26354,18611,2394,68363,64345,60985,725,33692,21195,60992,10243,62006,74884,7822,66830,16114,14663,60701,38174, d6047a481e 2014-07-05 kinaba: 30493,26360,7745,7165,47668,83884,89463,46615,7729,22187,78818,10817,31141,79159,24280,67585,48039,3000,98743,39455,12030,27595,55470,14617,93275, d6047a481e 2014-07-05 kinaba: 21233,72418,26911,74250,13704,68327,89871,72035,3437,97910,2325,83391,39732,79248,22431,93095,65547,74205,33341,2112,93431,32198,96772,20187,71348, d6047a481e 2014-07-05 kinaba: 19102,10840,27306,76027,86368,55373,40192,49370,90597,21685,23630,68099,50880,84474,61907,8446,30127,80977,53007,36125,47411,16950,7445,17166,71035, d6047a481e 2014-07-05 kinaba: 20293,24724,7404,6579,11282,83421,37466,80598,53398,15720,66117,28965,90631,44004,27582,29003,65915,35683,48237,66625,50977,82957,54602,3610,431,36560, d6047a481e 2014-07-05 kinaba: 38034,5948,72313,16772,81862,11871,33534,91097,93908,57721,91890,46009,21400,41257,66253,90004,56285,85267,23486,6953,66722,69568,74398,32371,15307, d6047a481e 2014-07-05 kinaba: 26503,31676,50683,46103,43963,90273,8938,41054,90794,95115,11689,61662,72089,12258,2816,4029,36441,17784,53116,4444,93653,63726,57293,38647,59684, d6047a481e 2014-07-05 kinaba: 72212,770,60745,25817,47807,85312,27451,51063,83640,2978,49906,744,69457,20244,8799,7,89118,78421,58827,38689,21327,32558,35756,53505,30526,39049, d6047a481e 2014-07-05 kinaba: 63417,24967,54923,62001,38920,59719,65486,174,52231,84176,83531,39896,70918,52397,5169,14876,92511,70020,88390,1168,35311,56953,12966,94805,3885, d6047a481e 2014-07-05 kinaba: 14103,24615,10710,27635,24064,23022,4506,29939,2044,48330,53688,41320,21646,62598,41367,22910,70284,11512,64411,16215,41072,87263,38301,81731,41930, d6047a481e 2014-07-05 kinaba: 96029,93359,32457,98487,62899,51282,8656,45002,83345,36991,77420,37086,53484,18823,74711,81453,81394,79933,38466,61198,98665,5528,9196,40298,55089, d6047a481e 2014-07-05 kinaba: 24162,99257,58066,90088,66809,53472,73237,31964,4792,42336,88141,80467,96893,44276,76106,79430,17072,85727,49790,84394,47215,16792,44544,75123,4203, d6047a481e 2014-07-05 kinaba: 6283,49250,54852,27312,42709,97204,16834,80593,27523,31700,44435,25338,43513,84894,43514,90145,74675,54302,85249,10281,44231,28994,63813,24198,24686, d6047a481e 2014-07-05 kinaba: 7082,46471,3025,57872,57510,13666,48726,3907,12500,53578,28346,15804,32122,89396,15406,11207,59571,78192,84950,84280,84597,27811,56165,69239,53400, d6047a481e 2014-07-05 kinaba: 32562,95679,32377,5909,29805,85810,31593,85985,27637,24974,41557,56442,48912,62362,98580,59154,78739,75721,72097,90622,91334,79685,19371,15487,67804, d6047a481e 2014-07-05 kinaba: 2582,26623,14347,98894,92041,83228,58089,96181,3913,75974,18569,11428,95165,27563}; d6047a481e 2014-07-05 kinaba: vector <int> weight(weight_, weight_+sizeof(weight_)/sizeof(*weight_)); d6047a481e 2014-07-05 kinaba: int charges = 160743953; d6047a481e 2014-07-05 kinaba: long long _ = -15328623718914LL; d6047a481e 2014-07-05 kinaba: END d6047a481e 2014-07-05 kinaba: CASE(4) d6047a481e 2014-07-05 kinaba: int N = 50; d6047a481e 2014-07-05 kinaba: int from_[] = {21,2,36,21,32,1,34,1,40,38,19,10,39,40,31,29,22,18,24,8,25,1,12,31,1,34,16,13,39,39,26,30,4,28,8,9,27,13,6,16,7,11,7,38,30,20,22,29,19,5,22,13,12,7, d6047a481e 2014-07-05 kinaba: 33,5,10,31,10,39,18,18,3,19,17,17,34,9,7,17,21,13,12,16,36,39,9,7,3,5,26,16,32,4,26,12,27,24,19,1,19,17,9,22,16,12,31,37,32,9,31,8,2,39,18,26,32,12, d6047a481e 2014-07-05 kinaba: 28,11,32,34,2,12,12,33,27,24,5,5,40,34,4,8,10,17,39,30,26,24,10,37,23,40,38,17,4,28,33,31,28,19,36,5,24,17,11,19,4,40,20,16,11,10,9,22,23,23,8,30,10, d6047a481e 2014-07-05 kinaba: 23,16,21,10,18,8,28,15,20,38,5,22,4,29,32,13,13,15,24,28,27,11,24,24,23,40,34,20,28,18,26,34,21,13,11,33,28,8,5,9,31,1,32,7,22,12,8,12,8,12,31,35,33, d6047a481e 2014-07-05 kinaba: 27,18,6,22,38,9,40,35,15,16,30,4,3,29,2,34,40,3,12,20,29,14,2,3,8,37,12,28,25,7,22,33,4,15,5,14,26,22,16,33,12,11,14,11,5,25,30,21,20,30,25,30,28,37, d6047a481e 2014-07-05 kinaba: 23,31,30,3,15,5,25,14,8,13,12,4,18,9,20,17,11,21,5,25,15,9,40,26,28,36,1,10,33,34,5,3,21,32,15,30,33,32,31,19,12,2,16,13,15,4,33,33,26,6,7,36,20,14,7, d6047a481e 2014-07-05 kinaba: 39,17,33,4,5,22,21,13,29,38,34,6,24,18,29,4,20,33,16,14,30,20,20,7,21,13,5,20,1,8,18,9,12,24,10,22,33,40,28,30,23,7,36,27,38,36,15,3,36,8,20,27,12,5, d6047a481e 2014-07-05 kinaba: 33,40,7,25,20,13,36,30,13,9,3,15,38,33,27,36,4,9,18,39,7,12,30,17,2,21,17,11,26,14,29,26,31,15,13,12,19,35,11,25,19,15,34,9,12,17,37,22,22,16,10,13, d6047a481e 2014-07-05 kinaba: 17,12,12,32,1,40,10,34,29,39,7,17,3,1,1,1,1,1,1,1,1,1,1}; d6047a481e 2014-07-05 kinaba: vector <int> from(from_, from_+sizeof(from_)/sizeof(*from_)); d6047a481e 2014-07-05 kinaba: int to_[] = {27,37,32,14,19,25,4,14,40,9,36,23,21,25,39,13,4,30,11,32,22,12,29,40,35,32,4,15,25,8,17,18,17,19,34,1,16,16,26,28,2,28,21,16,6,3,12,39,24,31,3,25,26, d6047a481e 2014-07-05 kinaba: 30,9,35,29,20,4,21,25,15,32,27,24,13,3,10,21,40,12,39,4,10,2,39,28,23,21,19,21,11,32,20,36,7,11,21,16,29,17,24,18,32,17,38,23,35,1,19,28,20,31,37,16, d6047a481e 2014-07-05 kinaba: 20,7,31,3,7,36,15,36,10,6,37,26,39,39,26,31,8,36,26,10,21,24,33,13,29,31,10,12,20,31,39,35,29,39,30,34,26,15,30,4,36,16,38,2,31,22,18,17,12,21,4,11, d6047a481e 2014-07-05 kinaba: 32,3,27,14,22,16,37,40,18,25,28,20,27,27,30,11,19,16,18,25,4,21,14,14,13,22,34,25,9,31,27,14,32,23,21,3,1,24,15,30,35,1,24,37,7,28,8,21,40,6,29,36,37, d6047a481e 2014-07-05 kinaba: 21,8,17,20,20,28,22,22,13,29,34,20,26,11,10,8,33,10,37,11,16,5,9,18,39,1,8,4,5,2,20,30,4,23,30,23,19,25,30,37,40,31,31,33,33,8,36,40,15,11,31,37,5,40, d6047a481e 2014-07-05 kinaba: 2,11,19,32,1,32,27,7,23,9,13,18,12,36,11,32,34,38,35,15,6,36,32,28,6,40,2,33,2,6,7,27,40,30,40,12,39,13,1,22,17,36,1,4,34,25,25,6,20,25,30,4,24,35,7,5, d6047a481e 2014-07-05 kinaba: 29,20,28,37,1,30,6,5,5,1,10,40,13,14,21,32,19,25,37,21,28,34,28,29,27,24,33,35,12,25,3,4,12,31,12,7,28,27,10,35,35,18,6,5,16,24,39,26,15,29,13,5,14,36, d6047a481e 2014-07-05 kinaba: 35,14,2,39,22,21,2,2,19,38,15,25,10,13,2,39,31,13,5,39,11,33,4,18,18,38,19,39,39,32,23,34,30,21,30,16,36,22,25,14,13,16,10,8,27,29,40,1,29,4,20,25,32, d6047a481e 2014-07-05 kinaba: 21,40,1,10,2,17,5,8,5,31,18,18,25,13,3,41,42,43,44,45,46,47,48,49,50}; d6047a481e 2014-07-05 kinaba: vector <int> to(to_, to_+sizeof(to_)/sizeof(*to_)); d6047a481e 2014-07-05 kinaba: int weight_[] = {93486,55539,34680,56705,10415,99106,26365,51838,20794,93178,33943,80260,60780,2405,78346,71929,24723,37614,62649,83486,32073,83866,88345,83213,28266, d6047a481e 2014-07-05 kinaba: 12730,27623,25353,89948,55002,36720,87151,39759,66091,3690,83881,82635,69084,54138,65876,54205,10236,90478,37230,22337,8209,14258,18375,5268,21824, d6047a481e 2014-07-05 kinaba: 76819,4094,63971,1454,21318,44848,92540,26354,18611,2394,68363,64345,60985,725,33692,21195,60992,10243,62006,74884,7822,66830,16114,14663,60701,38174, d6047a481e 2014-07-05 kinaba: 30493,26360,7745,7165,47668,83884,89463,46615,7729,22187,78818,10817,31141,79159,24280,67585,48039,3000,98743,39455,12030,27595,55470,14617,93275, d6047a481e 2014-07-05 kinaba: 21233,72418,26911,74250,13704,68327,89871,72035,3437,97910,2325,83391,39732,79248,22431,93095,65547,74205,33341,2112,93431,32198,96772,20187,71348, d6047a481e 2014-07-05 kinaba: 19102,10840,27306,76027,86368,55373,40192,49370,90597,21685,23630,68099,50880,84474,61907,8446,30127,80977,53007,36125,47411,16950,7445,17166,71035, d6047a481e 2014-07-05 kinaba: 20293,24724,7404,6579,11282,83421,37466,80598,53398,15720,66117,28965,90631,44004,27582,29003,65915,35683,48237,66625,50977,82957,54602,3610,431,36560, d6047a481e 2014-07-05 kinaba: 38034,5948,72313,16772,81862,11871,33534,91097,93908,57721,91890,46009,21400,41257,66253,90004,56285,85267,23486,6953,66722,69568,74398,32371,15307, d6047a481e 2014-07-05 kinaba: 26503,31676,50683,46103,43963,90273,8938,41054,90794,95115,11689,61662,72089,12258,2816,4029,36441,17784,53116,4444,93653,63726,57293,38647,59684, d6047a481e 2014-07-05 kinaba: 72212,770,60745,25817,47807,85312,27451,51063,83640,2978,49906,744,69457,20244,8799,7,89118,78421,58827,38689,21327,32558,35756,53505,30526,39049, d6047a481e 2014-07-05 kinaba: 63417,24967,54923,62001,38920,59719,65486,174,52231,84176,83531,39896,70918,52397,5169,14876,92511,70020,88390,1168,35311,56953,12966,94805,3885, d6047a481e 2014-07-05 kinaba: 14103,24615,10710,27635,24064,23022,4506,29939,2044,48330,53688,41320,21646,62598,41367,22910,70284,11512,64411,16215,41072,87263,38301,81731,41930, d6047a481e 2014-07-05 kinaba: 96029,93359,32457,98487,62899,51282,8656,45002,83345,36991,77420,37086,53484,18823,74711,81453,81394,79933,38466,61198,98665,5528,9196,40298,55089, d6047a481e 2014-07-05 kinaba: 24162,99257,58066,90088,66809,53472,73237,31964,4792,42336,88141,80467,96893,44276,76106,79430,17072,85727,49790,84394,47215,16792,44544,75123,4203, d6047a481e 2014-07-05 kinaba: 6283,49250,54852,27312,42709,97204,16834,80593,27523,31700,44435,25338,43513,84894,43514,90145,74675,54302,85249,10281,44231,28994,63813,24198,24686, d6047a481e 2014-07-05 kinaba: 7082,46471,3025,57872,57510,13666,48726,3907,12500,53578,28346,15804,32122,89396,15406,11207,59571,78192,84950,84280,84597,27811,56165,69239,53400, d6047a481e 2014-07-05 kinaba: 32562,95679,32377,5909,29805,85810,31593,85985,27637,24974,41557,56442,48912,62362,98580,59154,78739,75721,72097,90622,91334,79685,19371,15487,67804, d6047a481e 2014-07-05 kinaba: 2582,26623,14347,98894,92041,83228,58089,96181,3913,75974,18569,11428,95165,27563,10,10,10,10,10,10,10,10,10,10}; d6047a481e 2014-07-05 kinaba: vector <int> weight(weight_, weight_+sizeof(weight_)/sizeof(*weight_)); d6047a481e 2014-07-05 kinaba: int charges = 160743953; d6047a481e 2014-07-05 kinaba: long long _ = -15328623718914LL; d6047a481e 2014-07-05 kinaba: END d6047a481e 2014-07-05 kinaba: CASE(5) d6047a481e 2014-07-05 kinaba: int N = 2; d6047a481e 2014-07-05 kinaba: int from_[] = {1,1}; d6047a481e 2014-07-05 kinaba: vector <int> from(from_, from_+sizeof(from_)/sizeof(*from_)); d6047a481e 2014-07-05 kinaba: int to_[] = {2,2}; d6047a481e 2014-07-05 kinaba: vector <int> to(to_, to_+sizeof(to_)/sizeof(*to_)); d6047a481e 2014-07-05 kinaba: int weight_[] = {3,1}; d6047a481e 2014-07-05 kinaba: vector <int> weight(weight_, weight_+sizeof(weight_)/sizeof(*weight_)); d6047a481e 2014-07-05 kinaba: int charges = 1; d6047a481e 2014-07-05 kinaba: long long _ = -3LL; d6047a481e 2014-07-05 kinaba: END d6047a481e 2014-07-05 kinaba: /* d6047a481e 2014-07-05 kinaba: CASE(6) d6047a481e 2014-07-05 kinaba: int N = ; d6047a481e 2014-07-05 kinaba: int from_[] = ; d6047a481e 2014-07-05 kinaba: vector <int> from(from_, from_+sizeof(from_)/sizeof(*from_)); d6047a481e 2014-07-05 kinaba: int to_[] = ; d6047a481e 2014-07-05 kinaba: vector <int> to(to_, to_+sizeof(to_)/sizeof(*to_)); d6047a481e 2014-07-05 kinaba: int weight_[] = ; d6047a481e 2014-07-05 kinaba: vector <int> weight(weight_, weight_+sizeof(weight_)/sizeof(*weight_)); d6047a481e 2014-07-05 kinaba: int charges = ; d6047a481e 2014-07-05 kinaba: long long _ = LL; d6047a481e 2014-07-05 kinaba: END d6047a481e 2014-07-05 kinaba: */ d6047a481e 2014-07-05 kinaba: } d6047a481e 2014-07-05 kinaba: // END CUT HERE