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 63 6f 6d 70 ..#include <comp
00d0: 6c 65 78 3e 0d 0a 23 69 6e 63 6c 75 64 65 20 3c lex>..#include <
00e0: 71 75 65 75 65 3e 0d 0a 23 69 6e 63 6c 75 64 65 queue>..#include
00f0: 20 3c 73 74 61 63 6b 3e 0d 0a 23 69 6e 63 6c 75 <stack>..#inclu
0100: 64 65 20 3c 63 6d 61 74 68 3e 0d 0a 75 73 69 6e de <cmath>..usin
0110: 67 20 6e 61 6d 65 73 70 61 63 65 20 73 74 64 3b g namespace std;
0120: 0d 0a 74 79 70 65 64 65 66 20 6c 6f 6e 67 20 6c ..typedef long l
0130: 6f 6e 67 20 4c 4c 3b 0d 0a 0d 0a 0d 0a 63 6c 61 ong LL;......cla
0140: 73 73 20 4c 6f 6e 67 53 74 72 61 69 67 68 74 52 ss LongStraightR
0150: 6f 61 64 0d 0a 7b 0d 0a 70 75 62 6c 69 63 3a 0d oad..{..public:.
0160: 0a 09 74 79 70 65 64 65 66 20 70 61 69 72 3c 69 ..typedef pair<i
0170: 6e 74 2c 69 6e 74 3e 20 65 64 67 65 3b 20 2f 2f nt,int> edge; //
0180: 20 28 69 6e 64 65 78 2c 64 69 73 74 29 0d 0a 09 (index,dist)...
0190: 69 6e 74 20 64 69 73 74 61 6e 63 65 54 6f 44 65 int distanceToDe
01a0: 73 74 69 6e 61 74 69 6f 6e 28 76 65 63 74 6f 72 stination(vector
01b0: 3c 73 74 72 69 6e 67 3e 20 73 69 67 6e 73 2c 20 <string> signs,
01c0: 73 74 72 69 6e 67 20 64 65 73 74 69 6e 61 74 69 string destinati
01d0: 6f 6e 29 20 0d 0a 09 7b 0d 0a 09 09 69 6e 74 20 on) ...{....int
01e0: 6e 20 3d 20 73 69 67 6e 73 2e 73 69 7a 65 28 29 n = signs.size()
01f0: 3b 0d 0a 0d 0a 09 09 2f 2f 20 70 61 72 73 65 0d ;......// parse.
0200: 0a 09 09 76 65 63 74 6f 72 3c 20 6d 61 70 3c 73 ...vector< map<s
0210: 74 72 69 6e 67 2c 20 69 6e 74 3e 20 3e 20 64 61 tring, int> > da
0220: 74 61 28 6e 29 3b 0d 0a 09 09 6d 61 70 3c 73 74 ta(n);....map<st
0230: 72 69 6e 67 2c 20 76 65 63 74 6f 72 3c 65 64 67 ring, vector<edg
0240: 65 3e 20 3e 20 6e 32 64 3b 20 2f 2f 20 6e 61 6d e> > n2d; // nam
0250: 65 20 2d 3e 20 28 69 6e 64 65 78 2c 20 64 69 73 e -> (index, dis
0260: 74 29 0d 0a 09 09 66 6f 72 28 69 6e 74 20 69 3d t)....for(int i=
0270: 30 3b 20 69 3c 6e 3b 20 2b 2b 69 29 0d 0a 09 09 0; i<n; ++i)....
0280: 7b 0d 0a 09 09 09 73 74 72 69 6e 67 73 74 72 65 {.....stringstre
0290: 61 6d 20 73 69 6e 28 73 69 67 6e 73 5b 69 5d 29 am sin(signs[i])
02a0: 3b 0d 0a 09 09 09 77 68 69 6c 65 28 73 69 6e 29 ;.....while(sin)
02b0: 20 7b 0d 0a 09 09 09 09 73 74 72 69 6e 67 20 6e {......string n
02c0: 3b 20 69 6e 74 20 64 3b 20 73 69 6e 3e 3e 6e 3e ; int d; sin>>n>
02d0: 3e 64 3b 0d 0a 09 09 09 09 63 68 61 72 20 63 3b >d;......char c;
02e0: 20 73 69 6e 3e 3e 63 3b 20 2f 2f 20 27 3b 27 0d sin>>c; // ';'.
02f0: 0a 09 09 09 09 64 61 74 61 5b 69 5d 5b 6e 5d 20 .....data[i][n]
0300: 3d 20 64 3b 0d 0a 09 09 09 09 6e 32 64 5b 6e 5d = d;......n2d[n]
0310: 2e 70 75 73 68 5f 62 61 63 6b 28 20 65 64 67 65 .push_back( edge
0320: 28 69 2c 64 29 20 29 3b 0d 0a 09 09 09 7d 0d 0a (i,d) );.....}..
0330: 09 09 7d 0d 0a 0d 0a 09 09 2f 2f 20 63 6f 6e 73 ..}......// cons
0340: 74 72 75 63 74 20 74 68 65 20 67 72 61 70 68 0d truct the graph.
0350: 0a 09 09 76 65 63 74 6f 72 3c 20 76 65 63 74 6f ...vector< vecto
0360: 72 3c 65 64 67 65 3e 20 3e 20 47 28 6e 29 3b 0d r<edge> > G(n);.
0370: 0a 09 09 66 6f 72 28 69 6e 74 20 69 3d 30 3b 20 ...for(int i=0;
0380: 69 3c 6e 3b 20 2b 2b 69 29 0d 0a 09 09 7b 0d 0a i<n; ++i)....{..
0390: 09 09 09 66 6f 72 28 6d 61 70 3c 73 74 72 69 6e ...for(map<strin
03a0: 67 2c 69 6e 74 3e 3a 3a 69 74 65 72 61 74 6f 72 g,int>::iterator
03b0: 20 69 74 3d 64 61 74 61 5b 69 5d 2e 62 65 67 69 it=data[i].begi
03c0: 6e 28 29 3b 20 69 74 21 3d 64 61 74 61 5b 69 5d n(); it!=data[i]
03d0: 2e 65 6e 64 28 29 3b 20 2b 2b 69 74 29 0d 0a 09 .end(); ++it)...
03e0: 09 09 7b 0d 0a 09 09 09 09 76 65 63 74 6f 72 3c ..{......vector<
03f0: 65 64 67 65 3e 26 20 65 73 20 3d 20 6e 32 64 5b edge>& es = n2d[
0400: 69 74 2d 3e 66 69 72 73 74 5d 3b 0d 0a 09 09 09 it->first];.....
0410: 09 66 6f 72 28 69 6e 74 20 6a 3d 30 3b 20 6a 3c .for(int j=0; j<
0420: 65 73 2e 73 69 7a 65 28 29 3b 20 2b 2b 6a 29 0d es.size(); ++j).
0430: 0a 09 09 09 09 09 69 66 28 20 65 73 5b 6a 5d 2e ......if( es[j].
0440: 66 69 72 73 74 20 21 3d 20 69 20 29 0d 0a 09 09 first != i )....
0450: 09 09 09 09 47 5b 69 5d 2e 70 75 73 68 5f 62 61 ....G[i].push_ba
0460: 63 6b 28 20 65 64 67 65 28 65 73 5b 6a 5d 2e 66 ck( edge(es[j].f
0470: 69 72 73 74 2c 20 69 74 2d 3e 73 65 63 6f 6e 64 irst, it->second
0480: 20 2d 20 65 73 5b 6a 5d 2e 73 65 63 6f 6e 64 29 - es[j].second)
0490: 20 29 3b 0d 0a 09 09 09 7d 0d 0a 09 09 7d 0d 0a );.....}....}..
04a0: 0d 0a 09 09 74 72 79 20 7b 0d 0a 09 09 09 76 65 ....try {.....ve
04b0: 63 74 6f 72 3c 62 6f 6f 6c 3e 20 64 6f 6e 65 28 ctor<bool> done(
04c0: 6e 2c 20 66 61 6c 73 65 29 3b 0d 0a 09 09 09 76 n, false);.....v
04d0: 65 63 74 6f 72 3c 69 6e 74 3e 20 20 20 20 20 70 ector<int> p
04e0: 28 6e 29 3b 0d 0a 09 09 09 7b 0d 0a 09 09 09 09 (n);.....{......
04f0: 76 65 63 74 6f 72 3c 62 6f 6f 6c 3e 20 76 69 73 vector<bool> vis
0500: 69 74 65 64 28 6e 2c 20 66 61 6c 73 65 29 3b 0d ited(n, false);.
0510: 0a 09 09 09 09 64 66 73 28 6e 2d 31 2c 20 30 2c .....dfs(n-1, 0,
0520: 20 47 2c 20 76 69 73 69 74 65 64 2c 20 70 29 3b G, visited, p);
0530: 0d 0a 0d 0a 09 09 09 09 76 65 63 74 6f 72 3c 69 ........vector<i
0540: 6e 74 3e 20 6b 6e 3b 0d 0a 09 09 09 09 66 6f 72 nt> kn;......for
0550: 28 69 6e 74 20 69 3d 30 3b 20 69 3c 6e 3b 20 2b (int i=0; i<n; +
0560: 2b 69 29 0d 0a 09 09 09 09 09 69 66 28 20 76 69 +i).......if( vi
0570: 73 69 74 65 64 5b 69 5d 20 29 20 7b 0d 0a 09 09 sited[i] ) {....
0580: 09 09 09 09 6b 6e 2e 70 75 73 68 5f 62 61 63 6b ....kn.push_back
0590: 28 20 70 5b 69 5d 20 29 3b 0d 0a 09 09 09 09 09 ( p[i] );.......
05a0: 09 64 6f 6e 65 5b 69 5d 20 3d 20 74 72 75 65 3b .done[i] = true;
05b0: 0d 0a 09 09 09 09 09 7d 0d 0a 09 09 09 09 69 66 .......}......if
05c0: 28 20 21 73 6f 72 74 65 64 28 6b 6e 29 20 29 20 ( !sorted(kn) )
05d0: 7b 0d 0a 63 65 72 72 20 3c 3c 20 22 6e 73 31 22 {..cerr << "ns1"
05e0: 20 3c 3c 20 65 6e 64 6c 3b 0d 0a 09 09 09 09 09 << endl;.......
05f0: 72 65 74 75 72 6e 20 2d 31 3b 0d 0a 7d 0d 0a 09 return -1;..}...
0600: 09 09 7d 0d 0a 09 09 09 76 65 63 74 6f 72 3c 65 ..}.....vector<e
0610: 64 67 65 3e 26 20 65 73 20 3d 20 6e 32 64 5b 64 dge>& es = n2d[d
0620: 65 73 74 69 6e 61 74 69 6f 6e 5d 3b 0d 0a 09 09 estination];....
0630: 09 69 6e 74 20 72 65 73 75 6c 74 20 3d 20 70 5b .int result = p[
0640: 65 73 5b 30 5d 2e 66 69 72 73 74 5d 20 2b 20 65 es[0].first] + e
0650: 73 5b 30 5d 2e 73 65 63 6f 6e 64 3b 0d 0a 09 09 s[0].second;....
0660: 09 69 66 28 20 72 65 73 75 6c 74 20 3c 20 30 20 .if( result < 0
0670: 29 0d 0a 09 09 09 09 72 65 74 75 72 6e 20 2d 31 )......return -1
0680: 3b 0d 0a 0d 0a 09 09 09 66 6f 72 28 69 6e 74 20 ;.......for(int
0690: 76 3d 30 3b 20 76 3c 6e 3b 20 2b 2b 76 29 0d 0a v=0; v<n; ++v)..
06a0: 09 09 09 09 69 66 28 20 21 64 6f 6e 65 5b 76 5d ....if( !done[v]
06b0: 20 29 0d 0a 09 09 09 09 7b 0d 0a 09 09 09 09 09 )......{.......
06c0: 76 65 63 74 6f 72 3c 62 6f 6f 6c 3e 20 76 69 73 vector<bool> vis
06d0: 69 74 65 64 28 6e 2c 20 66 61 6c 73 65 29 3b 0d ited(n, false);.
06e0: 0a 09 09 09 09 09 64 66 73 28 76 2c 20 30 2c 20 ......dfs(v, 0,
06f0: 47 2c 20 76 69 73 69 74 65 64 2c 20 70 29 3b 0d G, visited, p);.
0700: 0a 0d 0a 09 09 09 09 09 76 65 63 74 6f 72 3c 69 ........vector<i
0710: 6e 74 3e 20 6b 6e 3b 0d 0a 09 09 09 09 09 66 6f nt> kn;.......fo
0720: 72 28 69 6e 74 20 69 3d 30 3b 20 69 3c 6e 3b 20 r(int i=0; i<n;
0730: 2b 2b 69 29 0d 0a 09 09 09 09 09 09 69 66 28 20 ++i)........if(
0740: 76 69 73 69 74 65 64 5b 69 5d 20 29 20 7b 0d 0a visited[i] ) {..
0750: 09 09 09 09 09 09 09 6b 6e 2e 70 75 73 68 5f 62 .......kn.push_b
0760: 61 63 6b 28 20 70 5b 69 5d 20 29 3b 0d 0a 09 09 ack( p[i] );....
0770: 09 09 09 09 09 64 6f 6e 65 5b 69 5d 20 3d 20 74 .....done[i] = t
0780: 72 75 65 3b 0d 0a 09 09 09 09 09 09 7d 0d 0a 09 rue;........}...
0790: 09 09 09 09 69 66 28 20 21 73 6f 72 74 65 64 28 ....if( !sorted(
07a0: 6b 6e 29 20 29 20 7b 0d 0a 63 65 72 72 20 3c 3c kn) ) {..cerr <<
07b0: 20 22 6e 73 40 22 20 3c 3c 20 76 20 3c 3c 20 65 "ns@" << v << e
07c0: 6e 64 6c 3b 0d 0a 09 09 09 09 09 09 72 65 74 75 ndl;........retu
07d0: 72 6e 20 2d 31 3b 0d 0a 7d 0d 0a 09 09 09 09 7d rn -1;..}......}
07e0: 0d 0a 09 09 09 72 65 74 75 72 6e 20 72 65 73 75 .....return resu
07f0: 6c 74 3b 0d 0a 09 09 7d 20 63 61 74 63 68 20 28 lt;....} catch (
0800: 63 6f 6e 73 74 20 63 68 61 72 2a 29 20 7b 0d 0a const char*) {..
0810: 09 09 09 72 65 74 75 72 6e 20 2d 31 3b 0d 0a 09 ...return -1;...
0820: 09 7d 0d 0a 09 7d 0d 0a 0d 0a 09 62 6f 6f 6c 20 .}...}.....bool
0830: 73 6f 72 74 65 64 28 20 76 65 63 74 6f 72 3c 69 sorted( vector<i
0840: 6e 74 3e 26 20 6b 6e 20 29 0d 0a 09 7b 0d 0a 09 nt>& kn )...{...
0850: 09 66 6f 72 28 69 6e 74 20 69 3d 30 3b 20 69 2b .for(int i=0; i+
0860: 31 3c 6b 6e 2e 73 69 7a 65 28 29 3b 20 2b 2b 69 1<kn.size(); ++i
0870: 29 0d 0a 09 09 09 69 66 28 20 6b 6e 5b 69 5d 20 ).....if( kn[i]
0880: 3e 3d 20 6b 6e 5b 69 2b 31 5d 20 29 0d 0a 09 09 >= kn[i+1] )....
0890: 09 09 72 65 74 75 72 6e 20 66 61 6c 73 65 3b 0d ..return false;.
08a0: 0a 09 09 72 65 74 75 72 6e 20 74 72 75 65 3b 0d ...return true;.
08b0: 0a 09 7d 0d 0a 0d 0a 09 76 6f 69 64 20 64 66 73 ..}.....void dfs
08c0: 28 69 6e 74 20 76 2c 20 69 6e 74 20 64 2c 20 76 (int v, int d, v
08d0: 65 63 74 6f 72 3c 20 76 65 63 74 6f 72 3c 65 64 ector< vector<ed
08e0: 67 65 3e 20 3e 26 20 47 2c 20 76 65 63 74 6f 72 ge> >& G, vector
08f0: 3c 62 6f 6f 6c 3e 26 20 76 69 73 69 74 65 64 2c <bool>& visited,
0900: 20 76 65 63 74 6f 72 3c 69 6e 74 3e 26 20 70 29 vector<int>& p)
0910: 0d 0a 09 7b 0d 0a 09 09 69 66 28 20 76 69 73 69 ...{....if( visi
0920: 74 65 64 5b 76 5d 20 29 20 7b 0d 0a 09 09 09 69 ted[v] ) {.....i
0930: 66 28 20 64 20 21 3d 20 70 5b 76 5d 20 29 20 7b f( d != p[v] ) {
0940: 0d 0a 63 65 72 72 20 3c 3c 20 64 20 3c 3c 20 22 ..cerr << d << "
0950: 20 22 20 3c 3c 20 76 20 3c 3c 20 22 20 22 20 3c " << v << " " <
0960: 3c 20 70 5b 76 5d 20 3c 3c 20 65 6e 64 6c 3b 0d < p[v] << endl;.
0970: 0a 09 09 09 09 74 68 72 6f 77 20 22 62 61 64 22 .....throw "bad"
0980: 3b 0d 0a 7d 0d 0a 09 09 09 72 65 74 75 72 6e 3b ;..}.....return;
0990: 0d 0a 09 09 7d 0d 0a 09 09 76 69 73 69 74 65 64 ....}....visited
09a0: 5b 76 5d 20 3d 20 74 72 75 65 3b 0d 0a 09 09 70 [v] = true;....p
09b0: 5b 76 5d 20 20 20 20 20 20 20 3d 20 64 3b 0d 0a [v] = d;..
09c0: 09 09 66 6f 72 28 69 6e 74 20 69 3d 30 3b 20 69 ..for(int i=0; i
09d0: 3c 47 5b 76 5d 2e 73 69 7a 65 28 29 3b 20 2b 2b <G[v].size(); ++
09e0: 69 29 20 7b 0d 0a 63 65 72 72 20 3c 3c 20 76 20 i) {..cerr << v
09f0: 3c 3c 20 22 2d 3e 22 20 3c 3c 20 47 5b 76 5d 5b << "->" << G[v][
0a00: 69 5d 2e 66 69 72 73 74 20 3c 3c 20 22 20 3a 20 i].first << " :
0a10: 22 20 3c 3c 20 47 5b 76 5d 5b 69 5d 2e 73 65 63 " << G[v][i].sec
0a20: 6f 6e 64 20 3c 3c 20 65 6e 64 6c 3b 0d 0a 09 09 ond << endl;....
0a30: 09 64 66 73 28 20 47 5b 76 5d 5b 69 5d 2e 66 69 .dfs( G[v][i].fi
0a40: 72 73 74 2c 20 64 2b 47 5b 76 5d 5b 69 5d 2e 73 rst, d+G[v][i].s
0a50: 65 63 6f 6e 64 2c 20 47 2c 20 76 69 73 69 74 65 econd, G, visite
0a60: 64 2c 20 70 20 29 3b 0d 0a 7d 0d 0a 09 7d 0d 0a d, p );..}...}..
0a70: 0d 0a 2f 2f 20 42 45 47 49 4e 20 43 55 54 20 48 ..// BEGIN CUT H
0a80: 45 52 45 0d 0a 09 70 75 62 6c 69 63 3a 0d 0a 09 ERE...public:...
0a90: 76 6f 69 64 20 72 75 6e 5f 74 65 73 74 28 69 6e void run_test(in
0aa0: 74 20 43 61 73 65 29 20 7b 20 69 66 20 28 28 43 t Case) { if ((C
0ab0: 61 73 65 20 3d 3d 20 2d 31 29 20 7c 7c 20 28 43 ase == -1) || (C
0ac0: 61 73 65 20 3d 3d 20 30 29 29 20 74 65 73 74 5f ase == 0)) test_
0ad0: 63 61 73 65 5f 30 28 29 3b 20 69 66 20 28 28 43 case_0(); if ((C
0ae0: 61 73 65 20 3d 3d 20 2d 31 29 20 7c 7c 20 28 43 ase == -1) || (C
0af0: 61 73 65 20 3d 3d 20 31 29 29 20 74 65 73 74 5f ase == 1)) test_
0b00: 63 61 73 65 5f 31 28 29 3b 20 69 66 20 28 28 43 case_1(); if ((C
0b10: 61 73 65 20 3d 3d 20 2d 31 29 20 7c 7c 20 28 43 ase == -1) || (C
0b20: 61 73 65 20 3d 3d 20 32 29 29 20 74 65 73 74 5f ase == 2)) test_
0b30: 63 61 73 65 5f 32 28 29 3b 20 69 66 20 28 28 43 case_2(); if ((C
0b40: 61 73 65 20 3d 3d 20 2d 31 29 20 7c 7c 20 28 43 ase == -1) || (C
0b50: 61 73 65 20 3d 3d 20 33 29 29 20 74 65 73 74 5f ase == 3)) test_
0b60: 63 61 73 65 5f 33 28 29 3b 20 69 66 20 28 28 43 case_3(); if ((C
0b70: 61 73 65 20 3d 3d 20 2d 31 29 20 7c 7c 20 28 43 ase == -1) || (C
0b80: 61 73 65 20 3d 3d 20 34 29 29 20 74 65 73 74 5f ase == 4)) test_
0b90: 63 61 73 65 5f 34 28 29 3b 20 7d 0d 0a 09 70 72 case_4(); }...pr
0ba0: 69 76 61 74 65 3a 0d 0a 09 74 65 6d 70 6c 61 74 ivate:...templat
0bb0: 65 20 3c 74 79 70 65 6e 61 6d 65 20 54 3e 20 73 e <typename T> s
0bc0: 74 72 69 6e 67 20 70 72 69 6e 74 5f 61 72 72 61 tring print_arra
0bd0: 79 28 63 6f 6e 73 74 20 76 65 63 74 6f 72 3c 54 y(const vector<T
0be0: 3e 20 26 56 29 20 7b 20 6f 73 74 72 69 6e 67 73 > &V) { ostrings
0bf0: 74 72 65 61 6d 20 6f 73 3b 20 6f 73 20 3c 3c 20 tream os; os <<
0c00: 22 7b 20 22 3b 20 66 6f 72 20 28 74 79 70 65 6e "{ "; for (typen
0c10: 61 6d 65 20 76 65 63 74 6f 72 3c 54 3e 3a 3a 63 ame vector<T>::c
0c20: 6f 6e 73 74 5f 69 74 65 72 61 74 6f 72 20 69 74 onst_iterator it
0c30: 65 72 20 3d 20 56 2e 62 65 67 69 6e 28 29 3b 20 er = V.begin();
0c40: 69 74 65 72 20 21 3d 20 56 2e 65 6e 64 28 29 3b iter != V.end();
0c50: 20 2b 2b 69 74 65 72 29 20 6f 73 20 3c 3c 20 27 ++iter) os << '
0c60: 5c 22 27 20 3c 3c 20 2a 69 74 65 72 20 3c 3c 20 \"' << *iter <<
0c70: 22 5c 22 2c 22 3b 20 6f 73 20 3c 3c 20 22 20 7d "\","; os << " }
0c80: 22 3b 20 72 65 74 75 72 6e 20 6f 73 2e 73 74 72 "; return os.str
0c90: 28 29 3b 20 7d 0d 0a 09 76 6f 69 64 20 76 65 72 (); }...void ver
0ca0: 69 66 79 5f 63 61 73 65 28 69 6e 74 20 43 61 73 ify_case(int Cas
0cb0: 65 2c 20 63 6f 6e 73 74 20 69 6e 74 20 26 45 78 e, const int &Ex
0cc0: 70 65 63 74 65 64 2c 20 63 6f 6e 73 74 20 69 6e pected, const in
0cd0: 74 20 26 52 65 63 65 69 76 65 64 29 20 7b 20 63 t &Received) { c
0ce0: 65 72 72 20 3c 3c 20 22 54 65 73 74 20 43 61 73 err << "Test Cas
0cf0: 65 20 23 22 20 3c 3c 20 43 61 73 65 20 3c 3c 20 e #" << Case <<
0d00: 22 2e 2e 2e 22 3b 20 69 66 20 28 45 78 70 65 63 "..."; if (Expec
0d10: 74 65 64 20 3d 3d 20 52 65 63 65 69 76 65 64 29 ted == Received)
0d20: 20 63 65 72 72 20 3c 3c 20 22 50 41 53 53 45 44 cerr << "PASSED
0d30: 22 20 3c 3c 20 65 6e 64 6c 3b 20 65 6c 73 65 20 " << endl; else
0d40: 7b 20 63 65 72 72 20 3c 3c 20 22 46 41 49 4c 45 { cerr << "FAILE
0d50: 44 22 20 3c 3c 20 65 6e 64 6c 3b 20 63 65 72 72 D" << endl; cerr
0d60: 20 3c 3c 20 22 5c 74 45 78 70 65 63 74 65 64 3a << "\tExpected:
0d70: 20 5c 22 22 20 3c 3c 20 45 78 70 65 63 74 65 64 \"" << Expected
0d80: 20 3c 3c 20 27 5c 22 27 20 3c 3c 20 65 6e 64 6c << '\"' << endl
0d90: 3b 20 63 65 72 72 20 3c 3c 20 22 5c 74 52 65 63 ; cerr << "\tRec
0da0: 65 69 76 65 64 3a 20 5c 22 22 20 3c 3c 20 52 65 eived: \"" << Re
0db0: 63 65 69 76 65 64 20 3c 3c 20 27 5c 22 27 20 3c ceived << '\"' <
0dc0: 3c 20 65 6e 64 6c 3b 20 7d 20 7d 0d 0a 09 76 6f < endl; } }...vo
0dd0: 69 64 20 74 65 73 74 5f 63 61 73 65 5f 30 28 29 id test_case_0()
0de0: 20 7b 20 73 74 72 69 6e 67 20 41 72 72 30 5b 5d { string Arr0[]
0df0: 20 3d 20 7b 22 43 4f 4c 43 48 45 53 54 45 52 20 = {"COLCHESTER
0e00: 35 3b 47 4c 41 53 54 4f 4e 42 55 52 59 20 32 35 5;GLASTONBURY 25
0e10: 3b 4d 41 52 4c 42 4f 52 4f 55 47 48 20 31 33 22 ;MARLBOROUGH 13"
0e20: 0d 0a 2c 22 4d 41 52 4c 42 4f 52 4f 55 47 48 20 ..,"MARLBOROUGH
0e30: 32 22 7d 3b 20 76 65 63 74 6f 72 20 3c 73 74 72 2"}; vector <str
0e40: 69 6e 67 3e 20 41 72 67 30 28 41 72 72 30 2c 20 ing> Arg0(Arr0,
0e50: 41 72 72 30 20 2b 20 28 73 69 7a 65 6f 66 28 41 Arr0 + (sizeof(A
0e60: 72 72 30 29 20 2f 20 73 69 7a 65 6f 66 28 41 72 rr0) / sizeof(Ar
0e70: 72 30 5b 30 5d 29 29 29 3b 20 73 74 72 69 6e 67 r0[0]))); string
0e80: 20 41 72 67 31 20 3d 20 22 47 4c 41 53 54 4f 4e Arg1 = "GLASTON
0e90: 42 55 52 59 22 3b 20 69 6e 74 20 41 72 67 32 20 BURY"; int Arg2
0ea0: 3d 20 31 34 3b 20 76 65 72 69 66 79 5f 63 61 73 = 14; verify_cas
0eb0: 65 28 30 2c 20 41 72 67 32 2c 20 64 69 73 74 61 e(0, Arg2, dista
0ec0: 6e 63 65 54 6f 44 65 73 74 69 6e 61 74 69 6f 6e nceToDestination
0ed0: 28 41 72 67 30 2c 20 41 72 67 31 29 29 3b 20 7d (Arg0, Arg1)); }
0ee0: 0d 0a 09 76 6f 69 64 20 74 65 73 74 5f 63 61 73 ...void test_cas
0ef0: 65 5f 31 28 29 20 7b 20 73 74 72 69 6e 67 20 41 e_1() { string A
0f00: 72 72 30 5b 5d 20 3d 20 7b 22 43 4f 4c 43 48 45 rr0[] = {"COLCHE
0f10: 53 54 45 52 20 35 3b 47 4c 41 53 54 4f 4e 42 55 STER 5;GLASTONBU
0f20: 52 59 20 32 35 3b 4d 41 52 4c 42 4f 52 4f 55 47 RY 25;MARLBOROUG
0f30: 48 20 31 33 22 0d 0a 2c 22 47 4c 41 53 54 4f 4e H 13"..,"GLASTON
0f40: 42 55 52 59 20 31 33 3b 4d 41 52 4c 42 4f 52 4f BURY 13;MARLBORO
0f50: 55 47 48 20 32 22 7d 3b 20 76 65 63 74 6f 72 20 UGH 2"}; vector
0f60: 3c 73 74 72 69 6e 67 3e 20 41 72 67 30 28 41 72 <string> Arg0(Ar
0f70: 72 30 2c 20 41 72 72 30 20 2b 20 28 73 69 7a 65 r0, Arr0 + (size
0f80: 6f 66 28 41 72 72 30 29 20 2f 20 73 69 7a 65 6f of(Arr0) / sizeo
0f90: 66 28 41 72 72 30 5b 30 5d 29 29 29 3b 20 73 74 f(Arr0[0]))); st
0fa0: 72 69 6e 67 20 41 72 67 31 20 3d 20 22 47 4c 41 ring Arg1 = "GLA
0fb0: 53 54 4f 4e 42 55 52 59 22 3b 20 69 6e 74 20 41 STONBURY"; int A
0fc0: 72 67 32 20 3d 20 2d 31 3b 20 76 65 72 69 66 79 rg2 = -1; verify
0fd0: 5f 63 61 73 65 28 31 2c 20 41 72 67 32 2c 20 64 _case(1, Arg2, d
0fe0: 69 73 74 61 6e 63 65 54 6f 44 65 73 74 69 6e 61 istanceToDestina
0ff0: 74 69 6f 6e 28 41 72 67 30 2c 20 41 72 67 31 29 tion(Arg0, Arg1)
1000: 29 3b 20 7d 0d 0a 09 76 6f 69 64 20 74 65 73 74 ); }...void test
1010: 5f 63 61 73 65 5f 32 28 29 20 7b 20 73 74 72 69 _case_2() { stri
1020: 6e 67 20 41 72 72 30 5b 5d 20 3d 20 7b 22 41 20 ng Arr0[] = {"A
1030: 32 35 3b 42 20 31 35 22 0d 0a 2c 22 41 20 32 22 25;B 15"..,"A 2"
1040: 7d 3b 20 76 65 63 74 6f 72 20 3c 73 74 72 69 6e }; vector <strin
1050: 67 3e 20 41 72 67 30 28 41 72 72 30 2c 20 41 72 g> Arg0(Arr0, Ar
1060: 72 30 20 2b 20 28 73 69 7a 65 6f 66 28 41 72 72 r0 + (sizeof(Arr
1070: 30 29 20 2f 20 73 69 7a 65 6f 66 28 41 72 72 30 0) / sizeof(Arr0
1080: 5b 30 5d 29 29 29 3b 20 73 74 72 69 6e 67 20 41 [0]))); string A
1090: 72 67 31 20 3d 20 22 42 22 3b 20 69 6e 74 20 41 rg1 = "B"; int A
10a0: 72 67 32 20 3d 20 2d 31 3b 20 76 65 72 69 66 79 rg2 = -1; verify
10b0: 5f 63 61 73 65 28 32 2c 20 41 72 67 32 2c 20 64 _case(2, Arg2, d
10c0: 69 73 74 61 6e 63 65 54 6f 44 65 73 74 69 6e 61 istanceToDestina
10d0: 74 69 6f 6e 28 41 72 67 30 2c 20 41 72 67 31 29 tion(Arg0, Arg1)
10e0: 29 3b 20 7d 0d 0a 09 76 6f 69 64 20 74 65 73 74 ); }...void test
10f0: 5f 63 61 73 65 5f 33 28 29 20 7b 20 73 74 72 69 _case_3() { stri
1100: 6e 67 20 41 72 72 30 5b 5d 20 3d 20 7b 22 59 56 ng Arr0[] = {"YV
1110: 4f 20 36 30 3b 4a 20 36 32 22 0d 0a 2c 22 4b 20 O 60;J 62"..,"K
1120: 34 35 22 0d 0a 2c 22 4b 20 34 30 3b 4d 56 20 31 45"..,"K 40;MV 1
1130: 37 22 0d 0a 2c 22 4b 20 33 37 3b 59 56 4f 20 34 7"..,"K 37;YVO 4
1140: 34 3b 48 59 20 34 38 3b 43 43 20 36 39 3b 44 20 4;HY 48;CC 69;D
1150: 37 37 3b 59 58 46 20 38 30 22 0d 0a 2c 22 59 56 77;YXF 80"..,"YV
1160: 4f 20 33 30 3b 42 20 33 37 3b 52 42 20 35 39 22 O 30;B 37;RB 59"
1170: 7d 3b 20 76 65 63 74 6f 72 20 3c 73 74 72 69 6e }; vector <strin
1180: 67 3e 20 41 72 67 30 28 41 72 72 30 2c 20 41 72 g> Arg0(Arr0, Ar
1190: 72 30 20 2b 20 28 73 69 7a 65 6f 66 28 41 72 72 r0 + (sizeof(Arr
11a0: 30 29 20 2f 20 73 69 7a 65 6f 66 28 41 72 72 30 0) / sizeof(Arr0
11b0: 5b 30 5d 29 29 29 3b 20 73 74 72 69 6e 67 20 41 [0]))); string A
11c0: 72 67 31 20 3d 20 22 4d 56 22 3b 20 69 6e 74 20 rg1 = "MV"; int
11d0: 41 72 67 32 20 3d 20 30 3b 20 76 65 72 69 66 79 Arg2 = 0; verify
11e0: 5f 63 61 73 65 28 33 2c 20 41 72 67 32 2c 20 64 _case(3, Arg2, d
11f0: 69 73 74 61 6e 63 65 54 6f 44 65 73 74 69 6e 61 istanceToDestina
1200: 74 69 6f 6e 28 41 72 67 30 2c 20 41 72 67 31 29 tion(Arg0, Arg1)
1210: 29 3b 20 7d 0d 0a 09 76 6f 69 64 20 74 65 73 74 ); }...void test
1220: 5f 63 61 73 65 5f 34 28 29 20 7b 20 73 74 72 69 _case_4() { stri
1230: 6e 67 20 41 72 72 30 5b 5d 20 3d 20 7b 22 41 20 ng Arr0[] = {"A
1240: 32 30 30 3b 42 20 31 35 30 22 0d 0a 2c 22 43 20 200;B 150"..,"C
1250: 34 35 3b 44 20 31 30 30 3b 45 20 31 35 30 22 0d 45;D 100;E 150".
1260: 0a 2c 22 43 20 32 35 3b 45 20 31 33 30 22 0d 0a .,"C 25;E 130"..
1270: 2c 22 46 20 38 30 3b 47 20 36 35 22 0d 0a 2c 22 ,"F 80;G 65"..,"
1280: 47 20 33 35 3b 48 20 31 36 30 22 0d 0a 2c 22 41 G 35;H 160"..,"A
1290: 20 31 36 30 22 0d 0a 2c 22 48 20 31 33 30 22 7d 160"..,"H 130"}
12a0: 3b 20 76 65 63 74 6f 72 20 3c 73 74 72 69 6e 67 ; vector <string
12b0: 3e 20 41 72 67 30 28 41 72 72 30 2c 20 41 72 72 > Arg0(Arr0, Arr
12c0: 30 20 2b 20 28 73 69 7a 65 6f 66 28 41 72 72 30 0 + (sizeof(Arr0
12d0: 29 20 2f 20 73 69 7a 65 6f 66 28 41 72 72 30 5b ) / sizeof(Arr0[
12e0: 30 5d 29 29 29 3b 20 73 74 72 69 6e 67 20 41 72 0]))); string Ar
12f0: 67 31 20 3d 20 22 46 22 3b 20 69 6e 74 20 41 72 g1 = "F"; int Ar
1300: 67 32 20 3d 20 2d 31 3b 20 76 65 72 69 66 79 5f g2 = -1; verify_
1310: 63 61 73 65 28 34 2c 20 41 72 67 32 2c 20 64 69 case(4, Arg2, di
1320: 73 74 61 6e 63 65 54 6f 44 65 73 74 69 6e 61 74 stanceToDestinat
1330: 69 6f 6e 28 41 72 67 30 2c 20 41 72 67 31 29 29 ion(Arg0, Arg1))
1340: 3b 20 7d 0d 0a 0d 0a 2f 2f 20 45 4e 44 20 43 55 ; }....// END CU
1350: 54 20 48 45 52 45 0d 0a 7d 3b 0d 0a 2f 2f 20 42 T HERE..};..// B
1360: 45 47 49 4e 20 43 55 54 20 48 45 52 45 20 0d 0a EGIN CUT HERE ..
1370: 69 6e 74 20 6d 61 69 6e 28 29 20 7b 0d 0a 09 4c int main() {...L
1380: 6f 6e 67 53 74 72 61 69 67 68 74 52 6f 61 64 28 ongStraightRoad(
1390: 29 2e 72 75 6e 5f 74 65 73 74 28 2d 31 29 3b 0d ).run_test(-1);.
13a0: 0a 7d 0d 0a 2f 2f 20 45 4e 44 20 43 55 54 20 48 .}..// END CUT H
13b0: 45 52 45 0d 0a ERE..