• branch=trunk inherited from [9165bd3629]
• sym-trunk inherited from [9165bd3629]

Added lib/graph/dijkstra.cpp version [f701e2736c51ff6e]

                                                                                        >     1  
                                                                                        >     2  //-------------------------------------------------------------
                                                                                        >     3  // Dijkstra's Algorithm
                                                                                        >     4  //   O(E log E)
                                                                                        >     5  //
                                                                                        >     6  // Need customization for
                                                                                        >     7  //   + infinite state space
                                                                                        >     8  //   + goal predicate
                                                                                        >     9  //   + path computation
                                                                                        >    10  //   + 1-to-all shortest distance
                                                                                        >    11  //
                                                                                        >    12  // Verified by
                                                                                        >    13  //   - Codeforces 77 Div1 C
                                                                                        >    14  //-------------------------------------------------------------
                                                                                        >    15  
                                                                                        >    16  template<typename T>
                                                                                        >    17  class IdGen
                                                                                        >    18  {
                                                                                        >    19          map<T, int> v2id_;
                                                                                        >    20          vector<T>   id2v_;
                                                                                        >    21  public:
                                                                                        >    22          int v2id(const T& v) {
                                                                                        >    23                  if( !v2id_.count(v) ) { v2id_[v] = size(); id2v_.push_back(v); }
                                                                                        >    24                  return v2id_[v];
                                                                                        >    25          }
                                                                                        >    26          const T& id2v(int i) const { return id2v_[i]; }
                                                                                        >    27          int size() const { return id2v_.size(); }
                                                                                        >    28  };
                                                                                        >    29  
                                                                                        >    30  template<typename Vert, typename Cost>
                                                                                        >    31  class Dijkstra
                                                                                        >    32  {
                                                                                        >    33          IdGen<Vert> idgen;
                                                                                        >    34  
                                                                                        >    35          typedef pair<Cost,int> Edge;
                                                                                        >    36          typedef vector<Edge>   Edges;
                                                                                        >    37          typedef vector<Edges>  Graph;
                                                                                        >    38          Graph G;
                                                                                        >    39  
                                                                                        >    40  public:
                                                                                        >    41          void addEdge( Vert s_, Vert t_, Cost c )
                                                                                        >    42          {
                                                                                        >    43                  int s = idgen.v2id(s_), t = idgen.v2id(t_);
                                                                                        >    44                  if( max(s,t) >= G.size() ) G.resize(max(s,t)+1);
                                                                                        >    45                  G[s].push_back(Edge(c, t));
                                                                                        >    46          }
                                                                                        >    47  
                                                                                        >    48          Cost calc( Vert s_, Vert t_ )
                                                                                        >    49          {
                                                                                        >    50                  int s = idgen.v2id(s_), t = idgen.v2id(t_);
                                                                                        >    51                  if( max(s,t) >= G.size() ) G.resize(max(s,t)+1);
                                                                                        >    52  
                                                                                        >    53                  priority_queue< Edge, vector<Edge>, greater<Edge> > Q;
                                                                                        >    54                  Q.push( Edge(0,s) );
                                                                                        >    55                  vector<bool> visited(G.size());
                                                                                        >    56                  while( !Q.empty() )
                                                                                        >    57                  {
                                                                                        >    58                          int  v = Q.top().second;
                                                                                        >    59                          Cost c = Q.top().first;
                                                                                        >    60                          Q.pop();
                                                                                        >    61                          if( visited[v] )
                                                                                        >    62                                  continue;
                                                                                        >    63                          visited[v] = true;
                                                                                        >    64  
                                                                                        >    65                          if( v == t )
                                                                                        >    66                                  return c;
                                                                                        >    67  
                                                                                        >    68                          for(int i=0; i<G[v].size(); ++i)
                                                                                        >    69                                  if( !visited[G[v][i].second] )
                                                                                        >    70                                          Q.push( make_pair(G[v][i].first+c, G[v][
                                                                                        >    71                  }
                                                                                        >    72                  return -1;
                                                                                        >    73          }
                                                                                        >    74  };