Artifact f701e2736c51ff6ef3b00e19e28b97e6458fa55d:
0000: 0a 2f 2f 2d 2d 2d 2d 2d 2d 2d 2d 2d 2d 2d 2d 2d .//-------------
0010: 2d 2d 2d 2d 2d 2d 2d 2d 2d 2d 2d 2d 2d 2d 2d 2d ----------------
0020: 2d 2d 2d 2d 2d 2d 2d 2d 2d 2d 2d 2d 2d 2d 2d 2d ----------------
0030: 2d 2d 2d 2d 2d 2d 2d 2d 2d 2d 2d 2d 2d 2d 2d 2d ----------------
0040: 0a 2f 2f 20 44 69 6a 6b 73 74 72 61 27 73 20 41 .// Dijkstra's A
0050: 6c 67 6f 72 69 74 68 6d 0a 2f 2f 20 20 20 4f 28 lgorithm.// O(
0060: 45 20 6c 6f 67 20 45 29 0a 2f 2f 0a 2f 2f 20 4e E log E).//.// N
0070: 65 65 64 20 63 75 73 74 6f 6d 69 7a 61 74 69 6f eed customizatio
0080: 6e 20 66 6f 72 0a 2f 2f 20 20 20 2b 20 69 6e 66 n for.// + inf
0090: 69 6e 69 74 65 20 73 74 61 74 65 20 73 70 61 63 inite state spac
00a0: 65 0a 2f 2f 20 20 20 2b 20 67 6f 61 6c 20 70 72 e.// + goal pr
00b0: 65 64 69 63 61 74 65 0a 2f 2f 20 20 20 2b 20 70 edicate.// + p
00c0: 61 74 68 20 63 6f 6d 70 75 74 61 74 69 6f 6e 0a ath computation.
00d0: 2f 2f 20 20 20 2b 20 31 2d 74 6f 2d 61 6c 6c 20 // + 1-to-all
00e0: 73 68 6f 72 74 65 73 74 20 64 69 73 74 61 6e 63 shortest distanc
00f0: 65 0a 2f 2f 0a 2f 2f 20 56 65 72 69 66 69 65 64 e.//.// Verified
0100: 20 62 79 0a 2f 2f 20 20 20 2d 20 43 6f 64 65 66 by.// - Codef
0110: 6f 72 63 65 73 20 37 37 20 44 69 76 31 20 43 0a orces 77 Div1 C.
0120: 2f 2f 2d 2d 2d 2d 2d 2d 2d 2d 2d 2d 2d 2d 2d 2d //--------------
0130: 2d 2d 2d 2d 2d 2d 2d 2d 2d 2d 2d 2d 2d 2d 2d 2d ----------------
0140: 2d 2d 2d 2d 2d 2d 2d 2d 2d 2d 2d 2d 2d 2d 2d 2d ----------------
0150: 2d 2d 2d 2d 2d 2d 2d 2d 2d 2d 2d 2d 2d 2d 2d 0a ---------------.
0160: 0a 74 65 6d 70 6c 61 74 65 3c 74 79 70 65 6e 61 .template<typena
0170: 6d 65 20 54 3e 0a 63 6c 61 73 73 20 49 64 47 65 me T>.class IdGe
0180: 6e 0a 7b 0a 09 6d 61 70 3c 54 2c 20 69 6e 74 3e n.{..map<T, int>
0190: 20 76 32 69 64 5f 3b 0a 09 76 65 63 74 6f 72 3c v2id_;..vector<
01a0: 54 3e 20 20 20 69 64 32 76 5f 3b 0a 70 75 62 6c T> id2v_;.publ
01b0: 69 63 3a 0a 09 69 6e 74 20 76 32 69 64 28 63 6f ic:..int v2id(co
01c0: 6e 73 74 20 54 26 20 76 29 20 7b 0a 09 09 69 66 nst T& v) {...if
01d0: 28 20 21 76 32 69 64 5f 2e 63 6f 75 6e 74 28 76 ( !v2id_.count(v
01e0: 29 20 29 20 7b 20 76 32 69 64 5f 5b 76 5d 20 3d ) ) { v2id_[v] =
01f0: 20 73 69 7a 65 28 29 3b 20 69 64 32 76 5f 2e 70 size(); id2v_.p
0200: 75 73 68 5f 62 61 63 6b 28 76 29 3b 20 7d 0a 09 ush_back(v); }..
0210: 09 72 65 74 75 72 6e 20 76 32 69 64 5f 5b 76 5d .return v2id_[v]
0220: 3b 0a 09 7d 0a 09 63 6f 6e 73 74 20 54 26 20 69 ;..}..const T& i
0230: 64 32 76 28 69 6e 74 20 69 29 20 63 6f 6e 73 74 d2v(int i) const
0240: 20 7b 20 72 65 74 75 72 6e 20 69 64 32 76 5f 5b { return id2v_[
0250: 69 5d 3b 20 7d 0a 09 69 6e 74 20 73 69 7a 65 28 i]; }..int size(
0260: 29 20 63 6f 6e 73 74 20 7b 20 72 65 74 75 72 6e ) const { return
0270: 20 69 64 32 76 5f 2e 73 69 7a 65 28 29 3b 20 7d id2v_.size(); }
0280: 0a 7d 3b 0a 0a 74 65 6d 70 6c 61 74 65 3c 74 79 .};..template<ty
0290: 70 65 6e 61 6d 65 20 56 65 72 74 2c 20 74 79 70 pename Vert, typ
02a0: 65 6e 61 6d 65 20 43 6f 73 74 3e 0a 63 6c 61 73 ename Cost>.clas
02b0: 73 20 44 69 6a 6b 73 74 72 61 0a 7b 0a 09 49 64 s Dijkstra.{..Id
02c0: 47 65 6e 3c 56 65 72 74 3e 20 69 64 67 65 6e 3b Gen<Vert> idgen;
02d0: 0a 0a 09 74 79 70 65 64 65 66 20 70 61 69 72 3c ...typedef pair<
02e0: 43 6f 73 74 2c 69 6e 74 3e 20 45 64 67 65 3b 0a Cost,int> Edge;.
02f0: 09 74 79 70 65 64 65 66 20 76 65 63 74 6f 72 3c .typedef vector<
0300: 45 64 67 65 3e 20 20 20 45 64 67 65 73 3b 0a 09 Edge> Edges;..
0310: 74 79 70 65 64 65 66 20 76 65 63 74 6f 72 3c 45 typedef vector<E
0320: 64 67 65 73 3e 20 20 47 72 61 70 68 3b 0a 09 47 dges> Graph;..G
0330: 72 61 70 68 20 47 3b 0a 0a 70 75 62 6c 69 63 3a raph G;..public:
0340: 0a 09 76 6f 69 64 20 61 64 64 45 64 67 65 28 20 ..void addEdge(
0350: 56 65 72 74 20 73 5f 2c 20 56 65 72 74 20 74 5f Vert s_, Vert t_
0360: 2c 20 43 6f 73 74 20 63 20 29 0a 09 7b 0a 09 09 , Cost c )..{...
0370: 69 6e 74 20 73 20 3d 20 69 64 67 65 6e 2e 76 32 int s = idgen.v2
0380: 69 64 28 73 5f 29 2c 20 74 20 3d 20 69 64 67 65 id(s_), t = idge
0390: 6e 2e 76 32 69 64 28 74 5f 29 3b 0a 09 09 69 66 n.v2id(t_);...if
03a0: 28 20 6d 61 78 28 73 2c 74 29 20 3e 3d 20 47 2e ( max(s,t) >= G.
03b0: 73 69 7a 65 28 29 20 29 20 47 2e 72 65 73 69 7a size() ) G.resiz
03c0: 65 28 6d 61 78 28 73 2c 74 29 2b 31 29 3b 0a 09 e(max(s,t)+1);..
03d0: 09 47 5b 73 5d 2e 70 75 73 68 5f 62 61 63 6b 28 .G[s].push_back(
03e0: 45 64 67 65 28 63 2c 20 74 29 29 3b 0a 09 7d 0a Edge(c, t));..}.
03f0: 0a 09 43 6f 73 74 20 63 61 6c 63 28 20 56 65 72 ..Cost calc( Ver
0400: 74 20 73 5f 2c 20 56 65 72 74 20 74 5f 20 29 0a t s_, Vert t_ ).
0410: 09 7b 0a 09 09 69 6e 74 20 73 20 3d 20 69 64 67 .{...int s = idg
0420: 65 6e 2e 76 32 69 64 28 73 5f 29 2c 20 74 20 3d en.v2id(s_), t =
0430: 20 69 64 67 65 6e 2e 76 32 69 64 28 74 5f 29 3b idgen.v2id(t_);
0440: 0a 09 09 69 66 28 20 6d 61 78 28 73 2c 74 29 20 ...if( max(s,t)
0450: 3e 3d 20 47 2e 73 69 7a 65 28 29 20 29 20 47 2e >= G.size() ) G.
0460: 72 65 73 69 7a 65 28 6d 61 78 28 73 2c 74 29 2b resize(max(s,t)+
0470: 31 29 3b 0a 0a 09 09 70 72 69 6f 72 69 74 79 5f 1);....priority_
0480: 71 75 65 75 65 3c 20 45 64 67 65 2c 20 76 65 63 queue< Edge, vec
0490: 74 6f 72 3c 45 64 67 65 3e 2c 20 67 72 65 61 74 tor<Edge>, great
04a0: 65 72 3c 45 64 67 65 3e 20 3e 20 51 3b 0a 09 09 er<Edge> > Q;...
04b0: 51 2e 70 75 73 68 28 20 45 64 67 65 28 30 2c 73 Q.push( Edge(0,s
04c0: 29 20 29 3b 0a 09 09 76 65 63 74 6f 72 3c 62 6f ) );...vector<bo
04d0: 6f 6c 3e 20 76 69 73 69 74 65 64 28 47 2e 73 69 ol> visited(G.si
04e0: 7a 65 28 29 29 3b 0a 09 09 77 68 69 6c 65 28 20 ze());...while(
04f0: 21 51 2e 65 6d 70 74 79 28 29 20 29 0a 09 09 7b !Q.empty() )...{
0500: 0a 09 09 09 69 6e 74 20 20 76 20 3d 20 51 2e 74 ....int v = Q.t
0510: 6f 70 28 29 2e 73 65 63 6f 6e 64 3b 0a 09 09 09 op().second;....
0520: 43 6f 73 74 20 63 20 3d 20 51 2e 74 6f 70 28 29 Cost c = Q.top()
0530: 2e 66 69 72 73 74 3b 0a 09 09 09 51 2e 70 6f 70 .first;....Q.pop
0540: 28 29 3b 0a 09 09 09 69 66 28 20 76 69 73 69 74 ();....if( visit
0550: 65 64 5b 76 5d 20 29 0a 09 09 09 09 63 6f 6e 74 ed[v] ).....cont
0560: 69 6e 75 65 3b 0a 09 09 09 76 69 73 69 74 65 64 inue;....visited
0570: 5b 76 5d 20 3d 20 74 72 75 65 3b 0a 0a 09 09 09 [v] = true;.....
0580: 69 66 28 20 76 20 3d 3d 20 74 20 29 0a 09 09 09 if( v == t )....
0590: 09 72 65 74 75 72 6e 20 63 3b 0a 0a 09 09 09 66 .return c;.....f
05a0: 6f 72 28 69 6e 74 20 69 3d 30 3b 20 69 3c 47 5b or(int i=0; i<G[
05b0: 76 5d 2e 73 69 7a 65 28 29 3b 20 2b 2b 69 29 0a v].size(); ++i).
05c0: 09 09 09 09 69 66 28 20 21 76 69 73 69 74 65 64 ....if( !visited
05d0: 5b 47 5b 76 5d 5b 69 5d 2e 73 65 63 6f 6e 64 5d [G[v][i].second]
05e0: 20 29 0a 09 09 09 09 09 51 2e 70 75 73 68 28 20 )......Q.push(
05f0: 6d 61 6b 65 5f 70 61 69 72 28 47 5b 76 5d 5b 69 make_pair(G[v][i
0600: 5d 2e 66 69 72 73 74 2b 63 2c 20 47 5b 76 5d 5b ].first+c, G[v][
0610: 69 5d 2e 73 65 63 6f 6e 64 29 20 29 3b 0a 09 09 i].second) );...
0620: 7d 0a 09 09 72 65 74 75 72 6e 20 2d 31 3b 0a 09 }...return -1;..
0630: 7d 0a 7d 3b 0a }.};.