Artifact f701e2736c51ff6ef3b00e19e28b97e6458fa55d
//-------------------------------------------------------------
// Dijkstra's Algorithm
// O(E log E)
//
// Need customization for
// + infinite state space
// + goal predicate
// + path computation
// + 1-to-all shortest distance
//
// Verified by
// - Codeforces 77 Div1 C
//-------------------------------------------------------------
template<typename T>
class IdGen
{
map<T, int> v2id_;
vector<T> id2v_;
public:
int v2id(const T& v) {
if( !v2id_.count(v) ) { v2id_[v] = size(); id2v_.push_back(v); }
return v2id_[v];
}
const T& id2v(int i) const { return id2v_[i]; }
int size() const { return id2v_.size(); }
};
template<typename Vert, typename Cost>
class Dijkstra
{
IdGen<Vert> idgen;
typedef pair<Cost,int> Edge;
typedef vector<Edge> Edges;
typedef vector<Edges> Graph;
Graph G;
public:
void addEdge( Vert s_, Vert t_, Cost c )
{
int s = idgen.v2id(s_), t = idgen.v2id(t_);
if( max(s,t) >= G.size() ) G.resize(max(s,t)+1);
G[s].push_back(Edge(c, t));
}
Cost calc( Vert s_, Vert t_ )
{
int s = idgen.v2id(s_), t = idgen.v2id(t_);
if( max(s,t) >= G.size() ) G.resize(max(s,t)+1);
priority_queue< Edge, vector<Edge>, greater<Edge> > Q;
Q.push( Edge(0,s) );
vector<bool> visited(G.size());
while( !Q.empty() )
{
int v = Q.top().second;
Cost c = Q.top().first;
Q.pop();
if( visited[v] )
continue;
visited[v] = true;
if( v == t )
return c;
for(int i=0; i<G[v].size(); ++i)
if( !visited[G[v][i].second] )
Q.push( make_pair(G[v][i].first+c, G[v][i].second) );
}
return -1;
}
};