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