0000: 23 69 6e 63 6c 75 64 65 20 3c 69 6f 73 74 72 65 #include <iostre
0010: 61 6d 3e 0d 0a 23 69 6e 63 6c 75 64 65 20 3c 73 am>..#include <s
0020: 73 74 72 65 61 6d 3e 0d 0a 23 69 6e 63 6c 75 64 stream>..#includ
0030: 65 20 3c 69 6f 6d 61 6e 69 70 3e 0d 0a 23 69 6e e <iomanip>..#in
0040: 63 6c 75 64 65 20 3c 76 65 63 74 6f 72 3e 0d 0a clude <vector>..
0050: 23 69 6e 63 6c 75 64 65 20 3c 73 74 72 69 6e 67 #include <string
0060: 3e 0d 0a 23 69 6e 63 6c 75 64 65 20 3c 6d 61 70 >..#include <map
0070: 3e 0d 0a 23 69 6e 63 6c 75 64 65 20 3c 73 65 74 >..#include <set
0080: 3e 0d 0a 23 69 6e 63 6c 75 64 65 20 3c 61 6c 67 >..#include <alg
0090: 6f 72 69 74 68 6d 3e 0d 0a 23 69 6e 63 6c 75 64 orithm>..#includ
00a0: 65 20 3c 6e 75 6d 65 72 69 63 3e 0d 0a 23 69 6e e <numeric>..#in
00b0: 63 6c 75 64 65 20 3c 69 74 65 72 61 74 6f 72 3e clude <iterator>
00c0: 0d 0a 23 69 6e 63 6c 75 64 65 20 3c 66 75 6e 63 ..#include <func
00d0: 74 69 6f 6e 61 6c 3e 0d 0a 23 69 6e 63 6c 75 64 tional>..#includ
00e0: 65 20 3c 63 6f 6d 70 6c 65 78 3e 0d 0a 23 69 6e e <complex>..#in
00f0: 63 6c 75 64 65 20 3c 71 75 65 75 65 3e 0d 0a 23 clude <queue>..#
0100: 69 6e 63 6c 75 64 65 20 3c 73 74 61 63 6b 3e 0d include <stack>.
0110: 0a 23 69 6e 63 6c 75 64 65 20 3c 63 6d 61 74 68 .#include <cmath
0120: 3e 0d 0a 23 69 6e 63 6c 75 64 65 20 3c 63 61 73 >..#include <cas
0130: 73 65 72 74 3e 0d 0a 23 69 6e 63 6c 75 64 65 20 sert>..#include
0140: 3c 74 75 70 6c 65 3e 0d 0a 75 73 69 6e 67 20 6e <tuple>..using n
0150: 61 6d 65 73 70 61 63 65 20 73 74 64 3b 0d 0a 74 amespace std;..t
0160: 79 70 65 64 65 66 20 6c 6f 6e 67 20 6c 6f 6e 67 ypedef long long
0170: 20 4c 4c 3b 0d 0a 74 79 70 65 64 65 66 20 63 6f LL;..typedef co
0180: 6d 70 6c 65 78 3c 64 6f 75 62 6c 65 3e 20 43 4d mplex<double> CM
0190: 50 3b 0d 0a 0d 0a 74 79 70 65 64 65 66 20 69 6e P;....typedef in
01a0: 74 20 56 65 72 74 3b 0d 0a 74 79 70 65 64 65 66 t Vert;..typedef
01b0: 20 4c 4c 20 43 6f 73 74 3b 0d 0a 74 79 70 65 64 LL Cost;..typed
01c0: 65 66 20 70 61 69 72 3c 43 6f 73 74 2c 56 65 72 ef pair<Cost,Ver
01d0: 74 3e 20 65 64 67 65 3b 0d 0a 74 79 70 65 64 65 t> edge;..typede
01e0: 66 20 76 65 63 74 6f 72 3c 65 64 67 65 3e 20 65 f vector<edge> e
01f0: 64 67 65 73 3b 0d 0a 74 79 70 65 64 65 66 20 76 dges;..typedef v
0200: 65 63 74 6f 72 3c 65 64 67 65 73 3e 20 67 72 61 ector<edges> gra
0210: 70 68 3b 0d 0a 63 6f 6e 73 74 20 4c 4c 20 49 4e ph;..const LL IN
0220: 46 20 3d 20 30 78 33 66 66 66 66 66 66 66 66 66 F = 0x3fffffffff
0230: 66 66 66 3b 0d 0a 0d 0a 63 6c 61 73 73 20 4d 61 fff;....class Ma
0240: 6c 69 63 69 6f 75 73 50 61 74 68 20 7b 20 70 75 liciousPath { pu
0250: 62 6c 69 63 3a 0d 0a 09 6c 6f 6e 67 20 6c 6f 6e blic:...long lon
0260: 67 20 6d 69 6e 50 61 74 68 28 69 6e 74 20 4e 2c g minPath(int N,
0270: 20 69 6e 74 20 4b 2c 20 76 65 63 74 6f 72 20 3c int K, vector <
0280: 69 6e 74 3e 20 66 72 6f 6d 2c 20 76 65 63 74 6f int> from, vecto
0290: 72 20 3c 69 6e 74 3e 20 74 6f 2c 20 76 65 63 74 r <int> to, vect
02a0: 6f 72 20 3c 69 6e 74 3e 20 63 6f 73 74 29 0d 0a or <int> cost)..
02b0: 09 7b 0d 0a 09 09 67 72 61 70 68 20 47 28 4e 29 .{....graph G(N)
02c0: 2c 20 47 72 28 4e 29 3b 0d 0a 09 09 66 6f 72 28 , Gr(N);....for(
02d0: 69 6e 74 20 69 3d 30 3b 20 69 3c 66 72 6f 6d 2e int i=0; i<from.
02e0: 73 69 7a 65 28 29 3b 20 2b 2b 69 29 20 7b 0d 0a size(); ++i) {..
02f0: 09 09 09 47 5b 66 72 6f 6d 5b 69 5d 5d 2e 65 6d ...G[from[i]].em
0300: 70 6c 61 63 65 5f 62 61 63 6b 28 63 6f 73 74 5b place_back(cost[
0310: 69 5d 2c 20 74 6f 5b 69 5d 29 3b 0d 0a 09 09 09 i], to[i]);.....
0320: 47 72 5b 74 6f 5b 69 5d 5d 2e 65 6d 70 6c 61 63 Gr[to[i]].emplac
0330: 65 5f 62 61 63 6b 28 63 6f 73 74 5b 69 5d 2c 20 e_back(cost[i],
0340: 66 72 6f 6d 5b 69 5d 29 3b 0d 0a 09 09 7d 0d 0a from[i]);....}..
0350: 0d 0a 09 09 76 65 63 74 6f 72 3c 43 6f 73 74 3e ....vector<Cost>
0360: 20 64 28 4e 2c 20 49 4e 46 29 3b 20 7b 0d 0a 09 d(N, INF); {...
0370: 09 09 70 72 69 6f 72 69 74 79 5f 71 75 65 75 65 ..priority_queue
0380: 3c 65 64 67 65 2c 20 65 64 67 65 73 2c 20 67 72 <edge, edges, gr
0390: 65 61 74 65 72 3c 65 64 67 65 3e 3e 20 51 3b 0d eater<edge>> Q;.
03a0: 0a 09 09 09 51 2e 65 6d 70 6c 61 63 65 28 30 2c ....Q.emplace(0,
03b0: 20 4e 2d 31 29 3b 0d 0a 09 09 09 77 68 69 6c 65 N-1);.....while
03c0: 28 21 51 2e 65 6d 70 74 79 28 29 29 20 7b 0d 0a (!Q.empty()) {..
03d0: 09 09 09 09 43 6f 73 74 20 63 20 3d 20 51 2e 74 ....Cost c = Q.t
03e0: 6f 70 28 29 2e 66 69 72 73 74 3b 0d 0a 09 09 09 op().first;.....
03f0: 09 56 65 72 74 20 76 20 3d 20 51 2e 74 6f 70 28 .Vert v = Q.top(
0400: 29 2e 73 65 63 6f 6e 64 3b 0d 0a 09 09 09 09 51 ).second;......Q
0410: 2e 70 6f 70 28 29 3b 0d 0a 09 09 09 09 69 66 28 .pop();......if(
0420: 64 5b 76 5d 20 3c 3d 20 63 29 0d 0a 09 09 09 09 d[v] <= c)......
0430: 09 63 6f 6e 74 69 6e 75 65 3b 0d 0a 09 09 09 09 .continue;......
0440: 64 5b 76 5d 20 3d 20 63 3b 0d 0a 09 09 09 09 66 d[v] = c;......f
0450: 6f 72 28 61 75 74 6f 20 65 3a 20 47 72 5b 76 5d or(auto e: Gr[v]
0460: 29 20 7b 0d 0a 09 09 09 09 09 43 6f 73 74 20 63 ) {.......Cost c
0470: 63 20 3d 20 63 20 2b 20 65 2e 66 69 72 73 74 3b c = c + e.first;
0480: 0d 0a 09 09 09 09 09 56 65 72 74 20 76 76 20 3d .......Vert vv =
0490: 20 65 2e 73 65 63 6f 6e 64 3b 0d 0a 09 09 09 09 e.second;......
04a0: 09 69 66 28 64 5b 76 76 5d 20 3d 3d 20 49 4e 46 .if(d[vv] == INF
04b0: 29 0d 0a 09 09 09 09 09 09 51 2e 65 6d 70 6c 61 )........Q.empla
04c0: 63 65 28 63 63 2c 20 76 76 29 3b 0d 0a 09 09 09 ce(cc, vv);.....
04d0: 09 7d 0d 0a 09 09 09 7d 0d 0a 09 09 09 69 66 28 .}.....}.....if(
04e0: 64 5b 30 5d 20 3d 3d 20 49 4e 46 29 0d 0a 09 09 d[0] == INF)....
04f0: 09 09 72 65 74 75 72 6e 20 2d 31 3b 0d 0a 09 09 ..return -1;....
0500: 7d 0d 0a 0d 0a 09 09 77 68 69 6c 65 28 4b 20 2d }......while(K -
0510: 2d 3e 20 30 29 20 7b 0d 0a 09 09 09 76 65 63 74 -> 0) {.....vect
0520: 6f 72 3c 43 6f 73 74 3e 20 64 32 28 4e 2c 20 30 or<Cost> d2(N, 0
0530: 29 3b 0d 0a 09 09 09 66 6f 72 28 56 65 72 74 20 );.....for(Vert
0540: 76 3d 30 3b 20 76 3c 4e 2d 31 3b 20 2b 2b 76 29 v=0; v<N-1; ++v)
0550: 20 7b 0d 0a 09 09 09 09 4c 4c 20 77 6f 72 73 74 {......LL worst
0560: 20 3d 20 30 3b 0d 0a 09 09 09 09 66 6f 72 28 61 = 0;......for(a
0570: 75 74 6f 20 65 3a 20 47 5b 76 5d 29 0d 0a 09 09 uto e: G[v])....
0580: 09 09 09 77 6f 72 73 74 20 3d 20 6d 61 78 28 77 ...worst = max(w
0590: 6f 72 73 74 2c 20 65 2e 66 69 72 73 74 2b 64 5b orst, e.first+d[
05a0: 65 2e 73 65 63 6f 6e 64 5d 29 3b 0d 0a 09 09 09 e.second]);.....
05b0: 09 64 32 5b 76 5d 20 3d 20 77 6f 72 73 74 3b 0d .d2[v] = worst;.
05c0: 0a 09 09 09 7d 0d 0a 0d 0a 09 09 09 64 2e 61 73 ....}.......d.as
05d0: 73 69 67 6e 28 4e 2c 20 49 4e 46 29 3b 0d 0a 0d sign(N, INF);...
05e0: 0a 09 09 09 70 72 69 6f 72 69 74 79 5f 71 75 65 ....priority_que
05f0: 75 65 3c 65 64 67 65 2c 20 65 64 67 65 73 2c 20 ue<edge, edges,
0600: 67 72 65 61 74 65 72 3c 65 64 67 65 3e 3e 20 51 greater<edge>> Q
0610: 3b 0d 0a 09 09 09 51 2e 65 6d 70 6c 61 63 65 28 ;.....Q.emplace(
0620: 30 2c 20 4e 2d 31 29 3b 0d 0a 09 09 09 77 68 69 0, N-1);.....whi
0630: 6c 65 28 21 51 2e 65 6d 70 74 79 28 29 29 20 7b le(!Q.empty()) {
0640: 0d 0a 09 09 09 09 43 6f 73 74 20 63 20 3d 20 51 ......Cost c = Q
0650: 2e 74 6f 70 28 29 2e 66 69 72 73 74 3b 0d 0a 09 .top().first;...
0660: 09 09 09 56 65 72 74 20 76 20 3d 20 51 2e 74 6f ...Vert v = Q.to
0670: 70 28 29 2e 73 65 63 6f 6e 64 3b 0d 0a 09 09 09 p().second;.....
0680: 09 51 2e 70 6f 70 28 29 3b 0d 0a 09 09 09 09 69 .Q.pop();......i
0690: 66 28 64 5b 76 5d 20 3c 3d 20 63 29 0d 0a 09 09 f(d[v] <= c)....
06a0: 09 09 09 63 6f 6e 74 69 6e 75 65 3b 0d 0a 09 09 ...continue;....
06b0: 09 09 69 66 28 63 20 3c 20 64 32 5b 76 5d 29 0d ..if(c < d2[v]).
06c0: 0a 09 09 09 09 09 63 6f 6e 74 69 6e 75 65 3b 0d ......continue;.
06d0: 0a 09 09 09 09 64 5b 76 5d 20 3d 20 63 3b 0d 0a .....d[v] = c;..
06e0: 09 09 09 09 66 6f 72 28 61 75 74 6f 20 65 3a 20 ....for(auto e:
06f0: 47 72 5b 76 5d 29 20 7b 0d 0a 09 09 09 09 09 56 Gr[v]) {.......V
0700: 65 72 74 20 76 76 20 3d 20 65 2e 73 65 63 6f 6e ert vv = e.secon
0710: 64 3b 0d 0a 09 09 09 09 09 43 6f 73 74 20 63 63 d;.......Cost cc
0720: 20 3d 20 6d 61 78 28 64 32 5b 76 76 5d 2c 20 63 = max(d2[vv], c
0730: 20 2b 20 65 2e 66 69 72 73 74 29 3b 0d 0a 09 09 + e.first);....
0740: 09 09 09 69 66 28 64 5b 76 76 5d 20 3d 3d 20 49 ...if(d[vv] == I
0750: 4e 46 29 0d 0a 09 09 09 09 09 09 51 2e 65 6d 70 NF)........Q.emp
0760: 6c 61 63 65 28 63 63 2c 20 76 76 29 3b 0d 0a 09 lace(cc, vv);...
0770: 09 09 09 7d 0d 0a 09 09 09 7d 0d 0a 09 09 7d 0d ...}.....}....}.
0780: 0a 0d 0a 09 09 72 65 74 75 72 6e 20 64 5b 30 5d .....return d[0]
0790: 3b 0d 0a 09 7d 0d 0a 7d 3b 0d 0a 0d 0a 2f 2f 20 ;...}..};....//
07a0: 42 45 47 49 4e 20 43 55 54 20 48 45 52 45 0d 0a BEGIN CUT HERE..
07b0: 23 69 6e 63 6c 75 64 65 20 3c 63 74 69 6d 65 3e #include <ctime>
07c0: 0d 0a 64 6f 75 62 6c 65 20 73 74 61 72 74 5f 74 ..double start_t
07d0: 69 6d 65 3b 20 73 74 72 69 6e 67 20 74 69 6d 65 ime; string time
07e0: 72 28 29 0d 0a 20 7b 20 6f 73 74 72 69 6e 67 73 r().. { ostrings
07f0: 74 72 65 61 6d 20 6f 73 3b 20 6f 73 20 3c 3c 20 tream os; os <<
0800: 22 20 28 22 20 3c 3c 20 69 6e 74 28 28 63 6c 6f " (" << int((clo
0810: 63 6b 28 29 2d 73 74 61 72 74 5f 74 69 6d 65 29 ck()-start_time)
0820: 2f 43 4c 4f 43 4b 53 5f 50 45 52 5f 53 45 43 2a /CLOCKS_PER_SEC*
0830: 31 30 30 30 29 20 3c 3c 20 22 20 6d 73 65 63 29 1000) << " msec)
0840: 22 3b 20 72 65 74 75 72 6e 20 6f 73 2e 73 74 72 "; return os.str
0850: 28 29 3b 20 7d 0d 0a 74 65 6d 70 6c 61 74 65 3c (); }..template<
0860: 74 79 70 65 6e 61 6d 65 20 54 3e 20 6f 73 74 72 typename T> ostr
0870: 65 61 6d 26 20 6f 70 65 72 61 74 6f 72 3c 3c 28 eam& operator<<(
0880: 6f 73 74 72 65 61 6d 26 20 6f 73 2c 20 63 6f 6e ostream& os, con
0890: 73 74 20 76 65 63 74 6f 72 3c 54 3e 26 20 76 29 st vector<T>& v)
08a0: 0d 0a 20 7b 20 6f 73 20 3c 3c 20 22 7b 20 22 3b .. { os << "{ ";
08b0: 0d 0a 20 20 20 66 6f 72 28 74 79 70 65 6e 61 6d .. for(typenam
08c0: 65 20 76 65 63 74 6f 72 3c 54 3e 3a 3a 63 6f 6e e vector<T>::con
08d0: 73 74 5f 69 74 65 72 61 74 6f 72 20 69 74 3d 76 st_iterator it=v
08e0: 2e 62 65 67 69 6e 28 29 3b 20 69 74 21 3d 76 2e .begin(); it!=v.
08f0: 65 6e 64 28 29 3b 20 2b 2b 69 74 29 0d 0a 20 20 end(); ++it)..
0900: 20 6f 73 20 3c 3c 20 27 5c 22 27 20 3c 3c 20 2a os << '\"' << *
0910: 69 74 20 3c 3c 20 27 5c 22 27 20 3c 3c 20 28 69 it << '\"' << (i
0920: 74 2b 31 3d 3d 76 2e 65 6e 64 28 29 20 3f 20 22 t+1==v.end() ? "
0930: 22 20 3a 20 22 2c 20 22 29 3b 20 6f 73 20 3c 3c " : ", "); os <<
0940: 20 22 20 7d 22 3b 20 72 65 74 75 72 6e 20 6f 73 " }"; return os
0950: 3b 20 7d 0d 0a 76 6f 69 64 20 76 65 72 69 66 79 ; }..void verify
0960: 5f 63 61 73 65 28 63 6f 6e 73 74 20 6c 6f 6e 67 _case(const long
0970: 20 6c 6f 6e 67 26 20 45 78 70 65 63 74 65 64 2c long& Expected,
0980: 20 63 6f 6e 73 74 20 6c 6f 6e 67 20 6c 6f 6e 67 const long long
0990: 26 20 52 65 63 65 69 76 65 64 29 20 7b 0d 0a 20 & Received) {..
09a0: 62 6f 6f 6c 20 6f 6b 20 3d 20 28 45 78 70 65 63 bool ok = (Expec
09b0: 74 65 64 20 3d 3d 20 52 65 63 65 69 76 65 64 29 ted == Received)
09c0: 3b 0d 0a 20 69 66 28 6f 6b 29 20 63 65 72 72 20 ;.. if(ok) cerr
09d0: 3c 3c 20 22 50 41 53 53 45 44 22 20 3c 3c 20 74 << "PASSED" << t
09e0: 69 6d 65 72 28 29 20 3c 3c 20 65 6e 64 6c 3b 20 imer() << endl;
09f0: 20 65 6c 73 65 20 7b 20 63 65 72 72 20 3c 3c 20 else { cerr <<
0a00: 22 46 41 49 4c 45 44 22 20 3c 3c 20 74 69 6d 65 "FAILED" << time
0a10: 72 28 29 20 3c 3c 20 65 6e 64 6c 3b 0d 0a 20 63 r() << endl;.. c
0a20: 65 72 72 20 3c 3c 20 22 5c 74 6f 3a 20 5c 22 22 err << "\to: \""
0a30: 20 3c 3c 20 45 78 70 65 63 74 65 64 20 3c 3c 20 << Expected <<
0a40: 27 5c 22 27 20 3c 3c 20 65 6e 64 6c 20 3c 3c 20 '\"' << endl <<
0a50: 22 5c 74 78 3a 20 5c 22 22 20 3c 3c 20 52 65 63 "\tx: \"" << Rec
0a60: 65 69 76 65 64 20 3c 3c 20 27 5c 22 27 20 3c 3c eived << '\"' <<
0a70: 20 65 6e 64 6c 3b 20 7d 20 7d 0d 0a 23 64 65 66 endl; } }..#def
0a80: 69 6e 65 20 43 41 53 45 28 4e 29 20 7b 63 65 72 ine CASE(N) {cer
0a90: 72 20 3c 3c 20 22 54 65 73 74 20 43 61 73 65 20 r << "Test Case
0aa0: 23 22 20 3c 3c 20 4e 20 3c 3c 20 22 2e 2e 2e 22 #" << N << "..."
0ab0: 20 3c 3c 20 66 6c 75 73 68 3b 20 73 74 61 72 74 << flush; start
0ac0: 5f 74 69 6d 65 3d 63 6c 6f 63 6b 28 29 3b 0d 0a _time=clock();..
0ad0: 23 64 65 66 69 6e 65 20 45 4e 44 09 20 76 65 72 #define END. ver
0ae0: 69 66 79 5f 63 61 73 65 28 5f 2c 20 4d 61 6c 69 ify_case(_, Mali
0af0: 63 69 6f 75 73 50 61 74 68 28 29 2e 6d 69 6e 50 ciousPath().minP
0b00: 61 74 68 28 4e 2c 20 4b 2c 20 66 72 6f 6d 2c 20 ath(N, K, from,
0b10: 74 6f 2c 20 63 6f 73 74 29 29 3b 7d 0d 0a 69 6e to, cost));}..in
0b20: 74 20 6d 61 69 6e 28 29 7b 0d 0a 0d 0a 43 41 53 t main(){....CAS
0b30: 45 28 30 29 0d 0a 09 69 6e 74 20 4e 20 3d 20 33 E(0)...int N = 3
0b40: 3b 20 0d 0a 09 69 6e 74 20 4b 20 3d 20 31 30 30 ; ...int K = 100
0b50: 30 3b 20 0d 0a 09 69 6e 74 20 66 72 6f 6d 5f 5b 0; ...int from_[
0b60: 5d 20 3d 20 7b 30 2c 31 2c 31 2c 32 7d 3b 0d 0a ] = {0,1,1,2};..
0b70: 09 20 20 76 65 63 74 6f 72 20 3c 69 6e 74 3e 20 . vector <int>
0b80: 66 72 6f 6d 28 66 72 6f 6d 5f 2c 20 66 72 6f 6d from(from_, from
0b90: 5f 2b 73 69 7a 65 6f 66 28 66 72 6f 6d 5f 29 2f _+sizeof(from_)/
0ba0: 73 69 7a 65 6f 66 28 2a 66 72 6f 6d 5f 29 29 3b sizeof(*from_));
0bb0: 20 0d 0a 09 69 6e 74 20 74 6f 5f 5b 5d 20 3d 20 ...int to_[] =
0bc0: 7b 31 2c 30 2c 32 2c 32 7d 3b 0d 0a 09 20 20 76 {1,0,2,2};... v
0bd0: 65 63 74 6f 72 20 3c 69 6e 74 3e 20 74 6f 28 74 ector <int> to(t
0be0: 6f 5f 2c 20 74 6f 5f 2b 73 69 7a 65 6f 66 28 74 o_, to_+sizeof(t
0bf0: 6f 5f 29 2f 73 69 7a 65 6f 66 28 2a 74 6f 5f 29 o_)/sizeof(*to_)
0c00: 29 3b 20 0d 0a 09 69 6e 74 20 63 6f 73 74 5f 5b ); ...int cost_[
0c10: 5d 20 3d 20 7b 33 2c 32 2c 31 2c 31 7d 3b 0d 0a ] = {3,2,1,1};..
0c20: 09 20 20 76 65 63 74 6f 72 20 3c 69 6e 74 3e 20 . vector <int>
0c30: 63 6f 73 74 28 63 6f 73 74 5f 2c 20 63 6f 73 74 cost(cost_, cost
0c40: 5f 2b 73 69 7a 65 6f 66 28 63 6f 73 74 5f 29 2f _+sizeof(cost_)/
0c50: 73 69 7a 65 6f 66 28 2a 63 6f 73 74 5f 29 29 3b sizeof(*cost_));
0c60: 20 0d 0a 09 6c 6f 6e 67 20 6c 6f 6e 67 20 5f 20 ...long long _
0c70: 3d 20 35 30 30 34 4c 4c 3b 20 0d 0a 45 4e 44 0d = 5004LL; ..END.
0c80: 0a 43 41 53 45 28 31 29 0d 0a 09 69 6e 74 20 4e .CASE(1)...int N
0c90: 20 3d 20 34 3b 20 0d 0a 09 69 6e 74 20 4b 20 3d = 4; ...int K =
0ca0: 20 31 3b 20 0d 0a 09 69 6e 74 20 66 72 6f 6d 5f 1; ...int from_
0cb0: 5b 5d 20 3d 20 7b 30 2c 30 2c 31 2c 31 2c 31 2c [] = {0,0,1,1,1,
0cc0: 32 2c 32 2c 33 7d 3b 0d 0a 09 20 20 76 65 63 74 2,2,3};... vect
0cd0: 6f 72 20 3c 69 6e 74 3e 20 66 72 6f 6d 28 66 72 or <int> from(fr
0ce0: 6f 6d 5f 2c 20 66 72 6f 6d 5f 2b 73 69 7a 65 6f om_, from_+sizeo
0cf0: 66 28 66 72 6f 6d 5f 29 2f 73 69 7a 65 6f 66 28 f(from_)/sizeof(
0d00: 2a 66 72 6f 6d 5f 29 29 3b 20 0d 0a 09 69 6e 74 *from_)); ...int
0d10: 20 74 6f 5f 5b 5d 20 3d 20 7b 31 2c 33 2c 30 2c to_[] = {1,3,0,
0d20: 32 2c 33 2c 32 2c 31 2c 33 7d 3b 0d 0a 09 20 20 2,3,2,1,3};...
0d30: 76 65 63 74 6f 72 20 3c 69 6e 74 3e 20 74 6f 28 vector <int> to(
0d40: 74 6f 5f 2c 20 74 6f 5f 2b 73 69 7a 65 6f 66 28 to_, to_+sizeof(
0d50: 74 6f 5f 29 2f 73 69 7a 65 6f 66 28 2a 74 6f 5f to_)/sizeof(*to_
0d60: 29 29 3b 20 0d 0a 09 69 6e 74 20 63 6f 73 74 5f )); ...int cost_
0d70: 5b 5d 20 3d 20 7b 30 2c 31 30 30 2c 31 30 33 2c [] = {0,100,103,
0d80: 30 2c 30 2c 33 34 2c 31 30 32 2c 33 33 7d 3b 0d 0,0,34,102,33};.
0d90: 0a 09 20 20 76 65 63 74 6f 72 20 3c 69 6e 74 3e .. vector <int>
0da0: 20 63 6f 73 74 28 63 6f 73 74 5f 2c 20 63 6f 73 cost(cost_, cos
0db0: 74 5f 2b 73 69 7a 65 6f 66 28 63 6f 73 74 5f 29 t_+sizeof(cost_)
0dc0: 2f 73 69 7a 65 6f 66 28 2a 63 6f 73 74 5f 29 29 /sizeof(*cost_))
0dd0: 3b 20 0d 0a 09 6c 6f 6e 67 20 6c 6f 6e 67 20 5f ; ...long long _
0de0: 20 3d 20 31 30 30 4c 4c 3b 20 0d 0a 45 4e 44 0d = 100LL; ..END.
0df0: 0a 43 41 53 45 28 32 29 0d 0a 09 69 6e 74 20 4e .CASE(2)...int N
0e00: 20 3d 20 31 30 3b 20 0d 0a 09 69 6e 74 20 4b 20 = 10; ...int K
0e10: 3d 20 35 3b 20 0d 0a 09 69 6e 74 20 66 72 6f 6d = 5; ...int from
0e20: 5f 5b 5d 20 3d 20 7b 30 2c 30 2c 31 2c 31 2c 32 _[] = {0,0,1,1,2
0e30: 2c 32 2c 33 2c 33 2c 34 2c 34 2c 34 2c 35 2c 35 ,2,3,3,4,4,4,5,5
0e40: 2c 36 2c 36 2c 37 2c 37 2c 38 2c 38 2c 39 2c 39 ,6,6,7,7,8,8,9,9
0e50: 7d 3b 0d 0a 09 20 20 76 65 63 74 6f 72 20 3c 69 };... vector <i
0e60: 6e 74 3e 20 66 72 6f 6d 28 66 72 6f 6d 5f 2c 20 nt> from(from_,
0e70: 66 72 6f 6d 5f 2b 73 69 7a 65 6f 66 28 66 72 6f from_+sizeof(fro
0e80: 6d 5f 29 2f 73 69 7a 65 6f 66 28 2a 66 72 6f 6d m_)/sizeof(*from
0e90: 5f 29 29 3b 20 0d 0a 09 69 6e 74 20 74 6f 5f 5b _)); ...int to_[
0ea0: 5d 20 3d 20 7b 31 2c 31 2c 32 2c 32 2c 33 2c 33 ] = {1,1,2,2,3,3
0eb0: 2c 34 2c 34 2c 35 2c 35 2c 34 2c 36 2c 36 2c 37 ,4,4,5,5,4,6,6,7
0ec0: 2c 37 2c 38 2c 38 2c 39 2c 39 2c 39 2c 39 7d 3b ,7,8,8,9,9,9,9};
0ed0: 0d 0a 09 20 20 76 65 63 74 6f 72 20 3c 69 6e 74 ... vector <int
0ee0: 3e 20 74 6f 28 74 6f 5f 2c 20 74 6f 5f 2b 73 69 > to(to_, to_+si
0ef0: 7a 65 6f 66 28 74 6f 5f 29 2f 73 69 7a 65 6f 66 zeof(to_)/sizeof
0f00: 28 2a 74 6f 5f 29 29 3b 20 0d 0a 09 69 6e 74 20 (*to_)); ...int
0f10: 63 6f 73 74 5f 5b 5d 20 3d 20 7b 32 2c 31 30 2c cost_[] = {2,10,
0f20: 31 30 2c 31 2c 32 2c 31 30 2c 31 30 2c 31 2c 32 10,1,2,10,10,1,2
0f30: 2c 31 30 2c 31 30 30 2c 31 30 2c 32 2c 31 2c 31 ,10,100,10,2,1,1
0f40: 30 2c 31 30 2c 32 2c 31 2c 31 30 2c 31 30 2c 31 0,10,2,1,10,10,1
0f50: 7d 3b 0d 0a 09 20 20 76 65 63 74 6f 72 20 3c 69 };... vector <i
0f60: 6e 74 3e 20 63 6f 73 74 28 63 6f 73 74 5f 2c 20 nt> cost(cost_,
0f70: 63 6f 73 74 5f 2b 73 69 7a 65 6f 66 28 63 6f 73 cost_+sizeof(cos
0f80: 74 5f 29 2f 73 69 7a 65 6f 66 28 2a 63 6f 73 74 t_)/sizeof(*cost
0f90: 5f 29 29 3b 20 0d 0a 09 6c 6f 6e 67 20 6c 6f 6e _)); ...long lon
0fa0: 67 20 5f 20 3d 20 35 31 34 4c 4c 3b 20 0d 0a 45 g _ = 514LL; ..E
0fb0: 4e 44 0d 0a 43 41 53 45 28 33 29 0d 0a 09 69 6e ND..CASE(3)...in
0fc0: 74 20 4e 20 3d 20 35 30 3b 20 0d 0a 09 69 6e 74 t N = 50; ...int
0fd0: 20 4b 20 3d 20 32 30 30 3b 20 0d 0a 09 69 6e 74 K = 200; ...int
0fe0: 20 66 72 6f 6d 5f 5b 5d 20 3d 20 7b 30 2c 31 33 from_[] = {0,13
0ff0: 2c 38 2c 31 37 2c 33 2c 38 2c 34 2c 32 31 2c 31 ,8,17,3,8,4,21,1
1000: 31 2c 32 30 2c 32 2c 31 38 2c 32 31 2c 32 2c 34 1,20,2,18,21,2,4
1010: 2c 39 2c 31 37 2c 30 2c 31 34 2c 31 30 2c 31 35 ,9,17,0,14,10,15
1020: 2c 31 38 2c 31 2c 32 32 2c 31 30 2c 31 34 2c 0d ,18,1,22,10,14,.
1030: 0a 31 39 2c 32 34 2c 35 2c 35 2c 31 32 2c 37 2c .19,24,5,5,12,7,
1040: 37 2c 31 36 2c 31 39 2c 31 33 2c 32 30 2c 31 35 7,16,19,13,20,15
1050: 2c 32 33 2c 36 2c 32 33 2c 39 2c 33 2c 36 2c 31 ,23,6,23,9,3,6,1
1060: 36 2c 31 31 2c 32 32 2c 32 34 2c 31 32 2c 31 2c 6,11,22,24,12,1,
1070: 32 35 2c 32 35 2c 0d 0a 32 36 2c 32 36 2c 32 37 25,25,..26,26,27
1080: 2c 32 37 2c 32 38 2c 32 38 2c 32 39 2c 32 39 2c ,27,28,28,29,29,
1090: 33 30 2c 33 30 2c 33 31 2c 33 31 2c 33 32 2c 33 30,30,31,31,32,3
10a0: 32 2c 33 33 2c 33 33 2c 33 34 2c 33 34 2c 33 35 2,33,33,34,34,35
10b0: 2c 33 35 2c 33 36 2c 33 36 2c 33 37 2c 0d 0a 33 ,35,36,36,37,..3
10c0: 37 2c 33 38 2c 33 38 2c 33 39 2c 33 39 2c 34 30 7,38,38,39,39,40
10d0: 2c 34 30 2c 34 31 2c 34 31 2c 34 32 2c 34 32 2c ,40,41,41,42,42,
10e0: 34 33 2c 34 33 2c 34 34 2c 34 34 2c 34 35 2c 34 43,43,44,44,45,4
10f0: 35 2c 34 36 2c 34 36 2c 34 37 2c 34 37 2c 34 38 5,46,46,47,47,48
1100: 2c 34 38 2c 0d 0a 34 39 2c 34 39 2c 33 37 2c 39 ,48,..49,49,37,9
1110: 2c 31 34 2c 30 2c 33 33 2c 32 30 2c 34 36 2c 32 ,14,0,33,20,46,2
1120: 36 2c 31 32 2c 31 31 2c 32 2c 37 2c 33 34 2c 31 6,12,11,2,7,34,1
1130: 39 2c 33 37 2c 35 2c 32 2c 31 37 2c 34 31 2c 31 9,37,5,2,17,41,1
1140: 36 2c 33 34 2c 31 33 2c 31 38 2c 0d 0a 33 35 2c 6,34,13,18,..35,
1150: 36 2c 31 34 2c 31 36 2c 32 35 2c 39 2c 31 30 2c 6,14,16,25,9,10,
1160: 35 2c 31 30 2c 37 2c 33 36 2c 34 35 2c 33 2c 36 5,10,7,36,45,3,6
1170: 2c 32 32 2c 33 32 2c 32 38 2c 34 35 2c 34 30 2c ,22,32,28,45,40,
1180: 31 36 2c 33 36 2c 32 38 2c 31 36 2c 33 34 2c 31 16,36,28,16,34,1
1190: 2c 0d 0a 39 2c 31 39 2c 31 38 2c 36 2c 31 35 2c ,..9,19,18,6,15,
11a0: 32 39 2c 31 32 2c 35 2c 34 34 2c 33 33 2c 34 39 29,12,5,44,33,49
11b0: 2c 31 34 2c 34 30 2c 31 2c 33 30 2c 32 31 2c 33 ,14,40,1,30,21,3
11c0: 37 2c 34 39 2c 31 2c 34 34 2c 34 32 2c 36 2c 33 7,49,1,44,42,6,3
11d0: 38 2c 31 2c 33 31 2c 0d 0a 34 30 2c 33 37 2c 33 8,1,31,..40,37,3
11e0: 34 2c 33 35 2c 36 2c 34 33 2c 32 39 2c 34 31 2c 4,35,6,43,29,41,
11f0: 34 38 2c 31 37 2c 34 2c 33 38 2c 32 36 2c 34 2c 48,17,4,38,26,4,
1200: 34 36 2c 34 33 2c 36 2c 32 37 2c 33 30 2c 30 2c 46,43,6,27,30,0,
1210: 31 36 2c 34 30 2c 33 33 2c 30 2c 34 32 2c 0d 0a 16,40,33,0,42,..
1220: 34 31 2c 31 30 2c 33 33 2c 34 37 2c 31 31 2c 33 41,10,33,47,11,3
1230: 37 2c 34 39 2c 32 35 2c 33 36 2c 32 30 2c 34 37 7,49,25,36,20,47
1240: 2c 31 32 2c 32 38 2c 31 37 2c 31 31 2c 31 37 2c ,12,28,17,11,17,
1250: 32 36 2c 32 36 2c 33 37 2c 33 34 2c 32 37 2c 31 26,26,37,34,27,1
1260: 37 2c 38 2c 0d 0a 32 2c 31 33 2c 34 33 2c 33 36 7,8,..2,13,43,36
1270: 2c 32 38 2c 31 2c 32 33 2c 32 39 2c 34 30 2c 31 ,28,1,23,29,40,1
1280: 38 2c 32 32 2c 30 2c 37 2c 33 30 2c 32 33 2c 33 8,22,0,7,30,23,3
1290: 2c 33 39 2c 35 2c 32 33 2c 32 38 2c 33 38 2c 34 ,39,5,23,28,38,4
12a0: 34 2c 31 39 2c 34 33 2c 31 35 2c 0d 0a 31 36 2c 4,19,43,15,..16,
12b0: 34 33 2c 35 2c 32 37 2c 32 34 2c 32 35 2c 37 2c 43,5,27,24,25,7,
12c0: 31 36 2c 33 38 2c 33 33 2c 33 33 2c 31 2c 39 2c 16,38,33,33,1,9,
12d0: 32 35 2c 34 37 2c 30 2c 33 31 2c 33 30 2c 32 39 25,47,0,31,30,29
12e0: 2c 34 2c 33 36 2c 34 39 2c 32 36 2c 36 2c 33 39 ,4,36,49,26,6,39
12f0: 2c 0d 0a 34 30 2c 32 38 2c 33 39 2c 34 38 2c 32 ,..40,28,39,48,2
1300: 36 2c 32 2c 31 35 2c 34 31 2c 34 32 2c 33 32 2c 6,2,15,41,42,32,
1310: 30 2c 33 35 2c 33 34 2c 32 38 2c 33 30 2c 34 30 0,35,34,28,30,40
1320: 2c 33 2c 33 33 2c 31 36 2c 31 35 2c 34 31 2c 34 ,3,33,16,15,41,4
1330: 35 2c 31 32 2c 33 33 2c 0d 0a 33 35 2c 31 36 2c 5,12,33,..35,16,
1340: 34 37 2c 33 34 2c 32 33 7d 3b 0d 0a 09 20 20 76 47,34,23};... v
1350: 65 63 74 6f 72 20 3c 69 6e 74 3e 20 66 72 6f 6d ector <int> from
1360: 28 66 72 6f 6d 5f 2c 20 66 72 6f 6d 5f 2b 73 69 (from_, from_+si
1370: 7a 65 6f 66 28 66 72 6f 6d 5f 29 2f 73 69 7a 65 zeof(from_)/size
1380: 6f 66 28 2a 66 72 6f 6d 5f 29 29 3b 20 0d 0a 09 of(*from_)); ...
1390: 69 6e 74 20 74 6f 5f 5b 5d 20 3d 20 7b 34 31 2c int to_[] = {41,
13a0: 34 32 2c 31 37 2c 30 2c 32 2c 37 2c 32 38 2c 33 42,17,0,2,7,28,3
13b0: 32 2c 33 31 2c 33 33 2c 36 2c 34 32 2c 31 31 2c 2,31,33,6,42,11,
13c0: 31 33 2c 37 2c 34 30 2c 34 37 2c 32 31 2c 34 2c 13,7,40,47,21,4,
13d0: 36 2c 31 39 2c 31 35 2c 34 2c 31 38 2c 33 30 2c 6,19,15,4,18,30,
13e0: 32 35 2c 0d 0a 32 2c 31 30 2c 33 30 2c 33 34 2c 25,..2,10,30,34,
13f0: 31 2c 34 37 2c 33 35 2c 32 33 2c 33 2c 30 2c 39 1,47,35,23,3,0,9
1400: 2c 32 35 2c 34 32 2c 32 31 2c 34 2c 36 2c 34 37 ,25,42,21,4,6,47
1410: 2c 33 32 2c 35 2c 34 30 2c 35 2c 30 2c 38 2c 34 ,32,5,40,5,0,8,4
1420: 39 2c 31 36 2c 32 39 2c 38 2c 0d 0a 31 31 2c 34 9,16,29,8,..11,4
1430: 32 2c 33 33 2c 33 35 2c 32 36 2c 32 37 2c 34 33 2,33,35,26,27,43
1440: 2c 33 35 2c 36 2c 31 34 2c 31 33 2c 34 34 2c 32 ,35,6,14,13,44,2
1450: 35 2c 31 33 2c 34 32 2c 32 2c 32 36 2c 31 37 2c 5,13,42,2,26,17,
1460: 33 2c 34 30 2c 33 31 2c 31 38 2c 31 32 2c 32 34 3,40,31,18,12,24
1470: 2c 0d 0a 33 37 2c 30 2c 33 37 2c 31 35 2c 34 34 ,..37,0,37,15,44
1480: 2c 33 35 2c 34 30 2c 31 30 2c 31 2c 33 35 2c 34 ,35,40,10,1,35,4
1490: 37 2c 33 36 2c 33 33 2c 32 2c 33 39 2c 32 33 2c 7,36,33,2,39,23,
14a0: 32 38 2c 33 32 2c 30 2c 36 2c 32 31 2c 33 33 2c 28,32,0,6,21,33,
14b0: 34 31 2c 30 2c 31 39 2c 0d 0a 31 36 2c 32 39 2c 41,0,19,..16,29,
14c0: 33 35 2c 31 36 2c 34 34 2c 36 2c 31 38 2c 31 37 35,16,44,6,18,17
14d0: 2c 32 2c 34 36 2c 34 31 2c 31 31 2c 32 37 2c 35 ,2,46,41,11,27,5
14e0: 2c 34 34 2c 31 2c 34 38 2c 31 35 2c 34 33 2c 38 ,44,1,48,15,43,8
14f0: 2c 34 31 2c 33 33 2c 31 36 2c 31 31 2c 34 35 2c ,41,33,16,11,45,
1500: 0d 0a 34 37 2c 31 39 2c 34 31 2c 31 34 2c 34 31 ..47,19,41,14,41
1510: 2c 38 2c 32 34 2c 31 33 2c 33 2c 34 34 2c 34 31 ,8,24,13,3,44,41
1520: 2c 34 32 2c 33 30 2c 33 31 2c 34 34 2c 32 31 2c ,42,30,31,44,21,
1530: 31 34 2c 34 33 2c 34 38 2c 30 2c 36 2c 32 35 2c 14,43,48,0,6,25,
1540: 33 38 2c 33 36 2c 31 34 2c 0d 0a 33 36 2c 32 32 38,36,14,..36,22
1550: 2c 34 33 2c 31 35 2c 32 30 2c 31 39 2c 33 37 2c ,43,15,20,19,37,
1560: 32 35 2c 31 37 2c 34 34 2c 31 37 2c 34 36 2c 38 25,17,44,17,46,8
1570: 2c 32 35 2c 33 33 2c 31 39 2c 34 32 2c 34 30 2c ,25,33,19,42,40,
1580: 34 32 2c 32 34 2c 31 35 2c 33 31 2c 33 34 2c 38 42,24,15,31,34,8
1590: 2c 0d 0a 34 31 2c 32 35 2c 32 30 2c 32 39 2c 32 ,..41,25,20,29,2
15a0: 2c 35 2c 34 33 2c 32 38 2c 33 33 2c 34 30 2c 33 ,5,43,28,33,40,3
15b0: 31 2c 32 37 2c 36 2c 32 31 2c 39 2c 33 35 2c 38 1,27,6,21,9,35,8
15c0: 2c 38 2c 32 36 2c 31 33 2c 31 31 2c 33 31 2c 34 ,8,26,13,11,31,4
15d0: 2c 34 2c 33 30 2c 33 34 2c 0d 0a 33 35 2c 31 2c ,4,30,34,..35,1,
15e0: 31 35 2c 31 31 2c 31 30 2c 32 34 2c 31 35 2c 32 15,11,10,24,15,2
15f0: 34 2c 32 33 2c 31 36 2c 32 34 2c 33 32 2c 39 2c 4,23,16,24,32,9,
1600: 31 2c 36 2c 31 37 2c 34 38 2c 36 2c 33 35 2c 31 1,6,17,48,6,35,1
1610: 39 2c 31 32 2c 35 2c 32 31 2c 32 33 2c 32 35 2c 9,12,5,21,23,25,
1620: 39 2c 0d 0a 31 37 2c 34 37 2c 31 39 2c 32 33 2c 9,..17,47,19,23,
1630: 32 32 2c 33 35 2c 31 39 2c 35 2c 31 2c 31 30 2c 22,35,19,5,1,10,
1640: 39 2c 34 31 2c 31 31 2c 34 35 2c 30 2c 32 33 2c 9,41,11,45,0,23,
1650: 30 2c 31 31 2c 33 39 2c 30 2c 31 37 2c 32 2c 31 0,11,39,0,17,2,1
1660: 38 2c 34 2c 31 37 2c 32 34 2c 30 2c 0d 0a 31 30 8,4,17,24,0,..10
1670: 2c 31 39 2c 34 2c 33 36 2c 32 32 2c 34 32 2c 31 ,19,4,36,22,42,1
1680: 38 2c 31 33 2c 34 38 2c 32 37 2c 31 31 2c 31 39 8,13,48,27,11,19
1690: 2c 32 38 2c 33 31 2c 33 39 2c 33 32 2c 34 38 2c ,28,31,39,32,48,
16a0: 32 2c 32 36 2c 33 38 2c 34 33 2c 33 38 2c 34 39 2,26,38,43,38,49
16b0: 2c 33 34 2c 0d 0a 33 37 2c 31 31 2c 39 2c 31 31 ,34,..37,11,9,11
16c0: 2c 31 34 2c 31 32 2c 39 2c 33 37 2c 30 2c 32 32 ,14,12,9,37,0,22
16d0: 2c 31 34 2c 31 35 2c 30 2c 38 2c 32 33 2c 37 2c ,14,15,0,8,23,7,
16e0: 34 33 2c 35 2c 38 2c 31 36 2c 34 37 7d 3b 0d 0a 43,5,8,16,47};..
16f0: 09 20 20 76 65 63 74 6f 72 20 3c 69 6e 74 3e 20 . vector <int>
1700: 74 6f 28 74 6f 5f 2c 20 74 6f 5f 2b 73 69 7a 65 to(to_, to_+size
1710: 6f 66 28 74 6f 5f 29 2f 73 69 7a 65 6f 66 28 2a of(to_)/sizeof(*
1720: 74 6f 5f 29 29 3b 20 0d 0a 09 69 6e 74 20 63 6f to_)); ...int co
1730: 73 74 5f 5b 5d 20 3d 20 7b 34 39 34 2c 38 34 38 st_[] = {494,848
1740: 33 30 35 2c 33 33 32 36 2c 36 30 30 38 2c 32 32 305,3326,6008,22
1750: 33 2c 32 2c 36 2c 36 37 33 2c 31 35 32 33 33 35 3,2,6,673,152335
1760: 2c 32 35 2c 37 31 33 39 30 39 2c 34 32 38 34 32 ,25,713909,42842
1770: 2c 31 32 32 2c 39 39 34 31 2c 33 36 31 38 35 33 ,122,9941,361853
1780: 2c 0d 0a 33 35 2c 32 30 31 35 37 2c 31 30 39 38 ,..35,20157,1098
1790: 2c 34 31 2c 38 33 36 39 33 2c 33 36 35 38 35 31 ,41,83693,365851
17a0: 2c 34 33 38 34 33 2c 36 32 32 2c 35 39 31 32 33 ,43843,622,59123
17b0: 30 2c 37 37 32 32 2c 32 34 38 39 2c 37 2c 38 36 0,7722,2489,7,86
17c0: 31 36 32 32 2c 32 31 32 37 32 2c 0d 0a 31 36 39 1622,21272,..169
17d0: 2c 31 31 35 33 2c 33 2c 37 2c 33 2c 35 37 37 30 ,1153,3,7,3,5770
17e0: 33 31 2c 32 34 35 32 32 2c 35 2c 32 34 31 2c 37 31,24522,5,241,7
17f0: 35 37 39 30 30 2c 31 31 30 33 36 2c 38 38 39 32 57900,11036,8892
1800: 2c 31 39 39 2c 37 2c 32 2c 31 2c 34 35 33 30 33 ,199,7,2,1,45303
1810: 31 2c 31 31 35 2c 0d 0a 31 33 2c 31 32 35 2c 36 1,115,..13,125,6
1820: 37 2c 33 35 2c 39 31 2c 33 33 34 32 37 2c 31 34 7,35,91,33427,14
1830: 2c 31 30 36 2c 32 30 33 37 34 39 2c 35 2c 31 38 ,106,203749,5,18
1840: 30 34 2c 34 35 34 33 2c 32 33 2c 31 2c 32 38 31 04,4543,23,1,281
1850: 2c 34 34 31 32 31 32 2c 31 38 2c 33 2c 0d 0a 31 ,441212,18,3,..1
1860: 31 36 32 39 2c 32 33 33 2c 33 38 38 31 38 38 2c 1629,233,388188,
1870: 31 30 2c 37 30 31 2c 37 36 31 37 30 2c 37 36 33 10,701,76170,763
1880: 2c 38 37 35 2c 31 31 36 30 36 2c 34 34 39 37 32 ,875,11606,44972
1890: 2c 36 34 34 39 2c 33 37 34 30 39 2c 38 33 35 31 ,6449,37409,8351
18a0: 36 2c 35 39 31 32 2c 0d 0a 36 2c 37 30 35 38 39 6,5912,..6,70589
18b0: 39 2c 32 36 37 35 39 2c 32 35 33 2c 35 38 30 35 9,26759,253,5805
18c0: 33 31 2c 31 34 32 31 35 2c 32 31 39 31 36 2c 38 31,14215,21916,8
18d0: 38 34 37 37 35 2c 33 30 2c 36 37 38 2c 35 39 34 84775,30,678,594
18e0: 30 2c 31 37 2c 34 38 30 38 33 30 2c 38 2c 0d 0a 0,17,480830,8,..
18f0: 36 31 2c 32 31 38 36 31 33 2c 36 38 33 33 35 32 61,218613,683352
1900: 2c 34 2c 35 35 37 35 38 39 2c 32 36 31 39 2c 33 ,4,557589,2619,3
1910: 36 35 38 2c 32 32 31 35 31 35 2c 31 35 38 32 35 658,221515,15825
1920: 2c 31 36 33 35 37 37 2c 32 35 2c 39 2c 31 2c 34 ,163577,25,9,1,4
1930: 2c 31 33 2c 32 2c 38 38 2c 0d 0a 31 34 37 2c 31 ,13,2,88,..147,1
1940: 31 30 31 36 33 2c 31 38 31 31 38 2c 32 2c 31 35 10163,18118,2,15
1950: 34 32 39 2c 32 31 31 38 37 32 2c 32 34 2c 31 2c 429,211872,24,1,
1960: 31 38 38 33 38 32 2c 31 32 35 30 30 2c 32 33 34 188382,12500,234
1970: 38 2c 31 39 30 2c 34 32 37 39 2c 34 30 2c 38 34 8,190,4279,40,84
1980: 32 38 2c 0d 0a 35 36 33 32 35 2c 39 33 33 31 35 28,..56325,93315
1990: 32 2c 32 33 31 35 32 33 2c 39 34 35 34 2c 32 31 2,231523,9454,21
19a0: 2c 34 38 35 35 2c 39 36 31 36 38 2c 31 37 32 32 ,4855,96168,1722
19b0: 2c 33 32 39 35 31 35 2c 37 37 2c 31 2c 33 2c 33 ,329515,77,1,3,3
19c0: 35 31 38 2c 31 30 39 32 36 2c 0d 0a 31 32 31 37 518,10926,..1217
19d0: 32 2c 34 2c 37 31 2c 31 38 31 39 37 36 2c 31 33 2,4,71,181976,13
19e0: 31 38 2c 39 2c 35 30 38 36 2c 39 30 35 2c 31 30 18,9,5086,905,10
19f0: 38 34 39 30 2c 38 30 31 36 34 2c 32 2c 31 30 32 8490,80164,2,102
1a00: 33 36 2c 31 39 37 2c 31 38 38 30 2c 31 37 34 32 36,197,1880,1742
1a10: 30 2c 0d 0a 36 31 34 36 35 30 2c 33 37 32 34 35 0,..614650,37245
1a20: 37 2c 31 33 39 31 38 2c 33 36 2c 31 37 2c 31 36 7,13918,36,17,16
1a30: 37 2c 36 2c 32 35 34 31 32 37 2c 35 31 32 2c 31 7,6,254127,512,1
1a40: 35 2c 33 34 31 34 33 36 2c 31 2c 31 38 36 2c 39 5,341436,1,186,9
1a50: 36 2c 37 2c 33 2c 34 32 2c 34 2c 0d 0a 33 2c 34 6,7,3,42,4,..3,4
1a60: 2c 34 39 32 35 39 38 2c 31 38 35 32 33 2c 31 37 ,492598,18523,17
1a70: 32 33 30 32 2c 31 2c 34 32 31 35 33 35 2c 33 39 2302,1,421535,39
1a80: 30 33 38 32 2c 32 39 35 32 2c 36 32 32 38 2c 38 0382,2952,6228,8
1a90: 37 31 2c 35 30 35 33 37 32 2c 31 33 31 32 36 36 71,505372,131266
1aa0: 2c 35 2c 0d 0a 37 34 33 39 30 32 2c 31 31 2c 33 ,5,..743902,11,3
1ab0: 34 2c 36 35 37 2c 34 37 31 37 2c 33 31 39 36 2c 4,657,4717,3196,
1ac0: 32 35 39 2c 31 39 32 35 30 34 2c 32 32 39 2c 36 259,192504,229,6
1ad0: 37 38 36 2c 32 38 2c 34 34 33 36 34 2c 32 31 31 786,28,44364,211
1ae0: 32 33 2c 38 2c 31 36 36 37 38 31 2c 0d 0a 38 38 23,8,166781,..88
1af0: 35 30 32 31 2c 32 2c 38 32 38 2c 34 39 37 2c 33 5021,2,828,497,3
1b00: 37 36 2c 32 34 37 30 37 2c 35 32 2c 31 2c 31 36 76,24707,52,1,16
1b10: 35 39 2c 31 39 34 30 32 2c 32 37 32 36 31 2c 38 59,19402,27261,8
1b20: 32 2c 34 37 33 2c 34 34 33 2c 31 30 38 39 2c 35 2,473,443,1089,5
1b30: 38 36 2c 32 30 2c 0d 0a 37 2c 32 33 39 32 37 37 86,20,..7,239277
1b40: 2c 32 37 31 33 32 2c 34 36 38 31 2c 37 36 31 2c ,27132,4681,761,
1b50: 31 30 36 34 34 2c 31 37 37 39 38 2c 31 2c 38 32 10644,17798,1,82
1b60: 30 33 30 36 2c 31 33 33 33 30 2c 31 39 2c 32 39 0306,13330,19,29
1b70: 33 31 36 37 2c 32 2c 34 2c 38 39 32 37 39 2c 0d 3167,2,4,89279,.
1b80: 0a 31 34 2c 31 2c 39 2c 31 38 30 32 33 2c 31 31 .14,1,9,18023,11
1b90: 36 35 2c 34 39 35 32 32 31 2c 33 32 33 30 34 2c 65,495221,32304,
1ba0: 35 33 38 2c 31 37 38 36 31 33 2c 31 2c 34 37 36 538,178613,1,476
1bb0: 34 2c 33 32 37 36 37 2c 31 31 34 2c 31 30 33 2c 4,32767,114,103,
1bc0: 31 2c 33 30 32 2c 34 32 38 2c 0d 0a 39 32 2c 39 1,302,428,..92,9
1bd0: 32 37 33 35 32 2c 32 32 32 37 30 2c 32 36 34 36 27352,22270,2646
1be0: 2c 33 35 39 39 2c 36 2c 31 36 33 36 32 2c 33 2c ,3599,6,16362,3,
1bf0: 34 2c 32 38 30 32 38 36 2c 33 33 38 2c 36 35 32 4,280286,338,652
1c00: 2c 32 2c 33 34 37 30 32 32 2c 32 33 2c 33 32 33 ,2,347022,23,323
1c10: 30 38 34 2c 0d 0a 33 33 33 38 2c 34 36 2c 35 38 084,..3338,46,58
1c20: 2c 31 32 36 33 2c 39 33 2c 34 36 39 39 32 2c 31 ,1263,93,46992,1
1c30: 39 31 31 32 2c 31 2c 31 39 34 39 39 2c 33 33 2c 9112,1,19499,33,
1c40: 38 30 37 36 30 30 2c 32 30 32 39 36 2c 31 36 38 807600,20296,168
1c50: 30 33 2c 39 31 31 32 39 34 2c 33 31 35 31 2c 0d 03,911294,3151,.
1c60: 0a 31 2c 37 39 33 2c 31 2c 31 2c 35 30 34 2c 36 .1,793,1,1,504,6
1c70: 32 32 30 39 2c 31 33 39 37 2c 35 32 37 32 36 2c 2209,1397,52726,
1c80: 33 36 35 30 2c 35 34 2c 33 36 33 30 2c 33 35 38 3650,54,3630,358
1c90: 34 38 30 2c 31 37 38 2c 33 39 34 2c 32 38 2c 31 480,178,394,28,1
1ca0: 33 37 34 33 36 2c 35 32 37 36 34 2c 0d 0a 31 32 37436,52764,..12
1cb0: 30 39 2c 31 35 39 39 7d 3b 0d 0a 09 20 20 76 65 09,1599};... ve
1cc0: 63 74 6f 72 20 3c 69 6e 74 3e 20 63 6f 73 74 28 ctor <int> cost(
1cd0: 63 6f 73 74 5f 2c 20 63 6f 73 74 5f 2b 73 69 7a cost_, cost_+siz
1ce0: 65 6f 66 28 63 6f 73 74 5f 29 2f 73 69 7a 65 6f eof(cost_)/sizeo
1cf0: 66 28 2a 63 6f 73 74 5f 29 29 3b 20 0d 0a 09 6c f(*cost_)); ...l
1d00: 6f 6e 67 20 6c 6f 6e 67 20 5f 20 3d 20 31 32 31 ong long _ = 121
1d10: 32 31 33 35 30 39 4c 4c 3b 20 0d 0a 45 4e 44 0d 213509LL; ..END.
1d20: 0a 43 41 53 45 28 34 29 0d 0a 09 69 6e 74 20 4e .CASE(4)...int N
1d30: 20 3d 20 32 30 3b 20 0d 0a 09 69 6e 74 20 4b 20 = 20; ...int K
1d40: 3d 20 31 30 30 30 3b 20 0d 0a 09 69 6e 74 20 66 = 1000; ...int f
1d50: 72 6f 6d 5f 5b 5d 20 3d 20 7b 30 2c 31 2c 32 2c rom_[] = {0,1,2,
1d60: 33 2c 34 2c 35 2c 36 2c 37 2c 38 2c 39 2c 31 30 3,4,5,6,7,8,9,10
1d70: 2c 31 31 2c 31 32 2c 31 33 2c 31 34 2c 31 35 2c ,11,12,13,14,15,
1d80: 31 36 2c 31 37 2c 31 38 2c 31 39 2c 31 38 7d 3b 16,17,18,19,18};
1d90: 0d 0a 09 20 20 76 65 63 74 6f 72 20 3c 69 6e 74 ... vector <int
1da0: 3e 20 66 72 6f 6d 28 66 72 6f 6d 5f 2c 20 66 72 > from(from_, fr
1db0: 6f 6d 5f 2b 73 69 7a 65 6f 66 28 66 72 6f 6d 5f om_+sizeof(from_
1dc0: 29 2f 73 69 7a 65 6f 66 28 2a 66 72 6f 6d 5f 29 )/sizeof(*from_)
1dd0: 29 3b 20 0d 0a 09 69 6e 74 20 74 6f 5f 5b 5d 20 ); ...int to_[]
1de0: 3d 20 7b 31 2c 32 2c 33 2c 34 2c 35 2c 36 2c 37 = {1,2,3,4,5,6,7
1df0: 2c 38 2c 39 2c 31 30 2c 31 31 2c 31 32 2c 31 33 ,8,9,10,11,12,13
1e00: 2c 31 34 2c 31 35 2c 31 36 2c 31 37 2c 31 38 2c ,14,15,16,17,18,
1e10: 31 39 2c 30 2c 30 7d 3b 0d 0a 09 20 20 76 65 63 19,0,0};... vec
1e20: 74 6f 72 20 3c 69 6e 74 3e 20 74 6f 28 74 6f 5f tor <int> to(to_
1e30: 2c 20 74 6f 5f 2b 73 69 7a 65 6f 66 28 74 6f 5f , to_+sizeof(to_
1e40: 29 2f 73 69 7a 65 6f 66 28 2a 74 6f 5f 29 29 3b )/sizeof(*to_));
1e50: 20 0d 0a 09 69 6e 74 20 63 6f 73 74 5f 5b 5d 20 ...int cost_[]
1e60: 3d 20 7b 31 30 30 30 30 30 30 2c 31 30 30 30 30 = {1000000,10000
1e70: 30 30 2c 31 30 30 30 30 30 30 2c 31 30 30 30 30 00,1000000,10000
1e80: 30 30 2c 31 30 30 30 30 30 30 2c 31 30 30 30 30 00,1000000,10000
1e90: 30 30 2c 31 30 30 30 30 30 30 2c 31 30 30 30 30 00,1000000,10000
1ea0: 30 30 2c 31 30 30 30 30 30 30 2c 31 30 30 30 30 00,1000000,10000
1eb0: 30 30 2c 0d 0a 31 30 30 30 30 30 30 2c 31 30 30 00,..1000000,100
1ec0: 30 30 30 30 2c 31 30 30 30 30 30 30 2c 31 30 30 0000,1000000,100
1ed0: 30 30 30 30 2c 31 30 30 30 30 30 30 2c 31 30 30 0000,1000000,100
1ee0: 30 30 30 30 2c 31 30 30 30 30 30 30 2c 31 30 30 0000,1000000,100
1ef0: 30 30 30 30 2c 31 30 30 30 30 30 30 2c 31 30 30 0000,1000000,100
1f00: 30 30 30 30 2c 0d 0a 31 30 30 30 30 30 30 7d 3b 0000,..1000000};
1f10: 0d 0a 09 20 20 76 65 63 74 6f 72 20 3c 69 6e 74 ... vector <int
1f20: 3e 20 63 6f 73 74 28 63 6f 73 74 5f 2c 20 63 6f > cost(cost_, co
1f30: 73 74 5f 2b 73 69 7a 65 6f 66 28 63 6f 73 74 5f st_+sizeof(cost_
1f40: 29 2f 73 69 7a 65 6f 66 28 2a 63 6f 73 74 5f 29 )/sizeof(*cost_)
1f50: 29 3b 20 0d 0a 09 6c 6f 6e 67 20 6c 6f 6e 67 20 ); ...long long
1f60: 5f 20 3d 20 31 39 30 31 39 30 30 30 30 30 30 4c _ = 19019000000L
1f70: 4c 3b 20 0d 0a 45 4e 44 0d 0a 43 41 53 45 28 35 L; ..END..CASE(5
1f80: 29 0d 0a 09 69 6e 74 20 4e 20 3d 20 32 3b 20 0d )...int N = 2; .
1f90: 0a 09 69 6e 74 20 4b 20 3d 20 30 3b 20 0d 0a 09 ..int K = 0; ...
1fa0: 69 6e 74 20 66 72 6f 6d 5f 5b 5d 20 3d 20 7b 30 int from_[] = {0
1fb0: 2c 31 7d 3b 0d 0a 09 20 20 76 65 63 74 6f 72 20 ,1};... vector
1fc0: 3c 69 6e 74 3e 20 66 72 6f 6d 28 66 72 6f 6d 5f <int> from(from_
1fd0: 2c 20 66 72 6f 6d 5f 2b 73 69 7a 65 6f 66 28 66 , from_+sizeof(f
1fe0: 72 6f 6d 5f 29 2f 73 69 7a 65 6f 66 28 2a 66 72 rom_)/sizeof(*fr
1ff0: 6f 6d 5f 29 29 3b 20 0d 0a 09 69 6e 74 20 74 6f om_)); ...int to
2000: 5f 5b 5d 20 3d 20 7b 30 2c 31 7d 3b 0d 0a 09 20 _[] = {0,1};...
2010: 20 76 65 63 74 6f 72 20 3c 69 6e 74 3e 20 74 6f vector <int> to
2020: 28 74 6f 5f 2c 20 74 6f 5f 2b 73 69 7a 65 6f 66 (to_, to_+sizeof
2030: 28 74 6f 5f 29 2f 73 69 7a 65 6f 66 28 2a 74 6f (to_)/sizeof(*to
2040: 5f 29 29 3b 20 0d 0a 09 69 6e 74 20 63 6f 73 74 _)); ...int cost
2050: 5f 5b 5d 20 3d 20 7b 35 2c 34 7d 3b 0d 0a 09 20 _[] = {5,4};...
2060: 20 76 65 63 74 6f 72 20 3c 69 6e 74 3e 20 63 6f vector <int> co
2070: 73 74 28 63 6f 73 74 5f 2c 20 63 6f 73 74 5f 2b st(cost_, cost_+
2080: 73 69 7a 65 6f 66 28 63 6f 73 74 5f 29 2f 73 69 sizeof(cost_)/si
2090: 7a 65 6f 66 28 2a 63 6f 73 74 5f 29 29 3b 20 0d zeof(*cost_)); .
20a0: 0a 09 6c 6f 6e 67 20 6c 6f 6e 67 20 5f 20 3d 20 ..long long _ =
20b0: 2d 31 4c 4c 3b 20 0d 0a 45 4e 44 0d 0a 2f 2a 0d -1LL; ..END../*.
20c0: 0a 43 41 53 45 28 36 29 0d 0a 09 69 6e 74 20 4e .CASE(6)...int N
20d0: 20 3d 20 3b 20 0d 0a 09 69 6e 74 20 4b 20 3d 20 = ; ...int K =
20e0: 3b 20 0d 0a 09 69 6e 74 20 66 72 6f 6d 5f 5b 5d ; ...int from_[]
20f0: 20 3d 20 3b 0d 0a 09 20 20 76 65 63 74 6f 72 20 = ;... vector
2100: 3c 69 6e 74 3e 20 66 72 6f 6d 28 66 72 6f 6d 5f <int> from(from_
2110: 2c 20 66 72 6f 6d 5f 2b 73 69 7a 65 6f 66 28 66 , from_+sizeof(f
2120: 72 6f 6d 5f 29 2f 73 69 7a 65 6f 66 28 2a 66 72 rom_)/sizeof(*fr
2130: 6f 6d 5f 29 29 3b 20 0d 0a 09 69 6e 74 20 74 6f om_)); ...int to
2140: 5f 5b 5d 20 3d 20 3b 0d 0a 09 20 20 76 65 63 74 _[] = ;... vect
2150: 6f 72 20 3c 69 6e 74 3e 20 74 6f 28 74 6f 5f 2c or <int> to(to_,
2160: 20 74 6f 5f 2b 73 69 7a 65 6f 66 28 74 6f 5f 29 to_+sizeof(to_)
2170: 2f 73 69 7a 65 6f 66 28 2a 74 6f 5f 29 29 3b 20 /sizeof(*to_));
2180: 0d 0a 09 69 6e 74 20 63 6f 73 74 5f 5b 5d 20 3d ...int cost_[] =
2190: 20 3b 0d 0a 09 20 20 76 65 63 74 6f 72 20 3c 69 ;... vector <i
21a0: 6e 74 3e 20 63 6f 73 74 28 63 6f 73 74 5f 2c 20 nt> cost(cost_,
21b0: 63 6f 73 74 5f 2b 73 69 7a 65 6f 66 28 63 6f 73 cost_+sizeof(cos
21c0: 74 5f 29 2f 73 69 7a 65 6f 66 28 2a 63 6f 73 74 t_)/sizeof(*cost
21d0: 5f 29 29 3b 20 0d 0a 09 6c 6f 6e 67 20 6c 6f 6e _)); ...long lon
21e0: 67 20 5f 20 3d 20 4c 4c 3b 20 0d 0a 45 4e 44 0d g _ = LL; ..END.
21f0: 0a 43 41 53 45 28 37 29 0d 0a 09 69 6e 74 20 4e .CASE(7)...int N
2200: 20 3d 20 3b 20 0d 0a 09 69 6e 74 20 4b 20 3d 20 = ; ...int K =
2210: 3b 20 0d 0a 09 69 6e 74 20 66 72 6f 6d 5f 5b 5d ; ...int from_[]
2220: 20 3d 20 3b 0d 0a 09 20 20 76 65 63 74 6f 72 20 = ;... vector
2230: 3c 69 6e 74 3e 20 66 72 6f 6d 28 66 72 6f 6d 5f <int> from(from_
2240: 2c 20 66 72 6f 6d 5f 2b 73 69 7a 65 6f 66 28 66 , from_+sizeof(f
2250: 72 6f 6d 5f 29 2f 73 69 7a 65 6f 66 28 2a 66 72 rom_)/sizeof(*fr
2260: 6f 6d 5f 29 29 3b 20 0d 0a 09 69 6e 74 20 74 6f om_)); ...int to
2270: 5f 5b 5d 20 3d 20 3b 0d 0a 09 20 20 76 65 63 74 _[] = ;... vect
2280: 6f 72 20 3c 69 6e 74 3e 20 74 6f 28 74 6f 5f 2c or <int> to(to_,
2290: 20 74 6f 5f 2b 73 69 7a 65 6f 66 28 74 6f 5f 29 to_+sizeof(to_)
22a0: 2f 73 69 7a 65 6f 66 28 2a 74 6f 5f 29 29 3b 20 /sizeof(*to_));
22b0: 0d 0a 09 69 6e 74 20 63 6f 73 74 5f 5b 5d 20 3d ...int cost_[] =
22c0: 20 3b 0d 0a 09 20 20 76 65 63 74 6f 72 20 3c 69 ;... vector <i
22d0: 6e 74 3e 20 63 6f 73 74 28 63 6f 73 74 5f 2c 20 nt> cost(cost_,
22e0: 63 6f 73 74 5f 2b 73 69 7a 65 6f 66 28 63 6f 73 cost_+sizeof(cos
22f0: 74 5f 29 2f 73 69 7a 65 6f 66 28 2a 63 6f 73 74 t_)/sizeof(*cost
2300: 5f 29 29 3b 20 0d 0a 09 6c 6f 6e 67 20 6c 6f 6e _)); ...long lon
2310: 67 20 5f 20 3d 20 4c 4c 3b 20 0d 0a 45 4e 44 0d g _ = LL; ..END.
2320: 0a 2a 2f 0d 0a 7d 0d 0a 2f 2f 20 45 4e 44 20 43 .*/..}..// END C
2330: 55 54 20 48 45 52 45 0d 0a UT HERE..