• 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][i].second) );
           71  +  }
           72  +  return -1;
           73  + }
           74  +};