ADDED   lib/graph/dijkstra.cpp
Index: lib/graph/dijkstra.cpp
==================================================================
--- lib/graph/dijkstra.cpp
+++ lib/graph/dijkstra.cpp
@@ -0,0 +1,74 @@
+
+//-------------------------------------------------------------
+// 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;
+	}
+};