#include <lemon/smart_graph.h>

 #include <lemon/dijkstra.h>

 #include <lemon/maps.h>

 #include <lemon/xy.h>

 #include <lemon/graph_reader.h>

 #include <lemon/time_measure.h>

 #include <cmath>

 using namespace lemon;

 template <typename CoordMap>

 class PotentialMap {

 public:

   typedef double Value;

   typedef typename CoordMap::Key Key;

   PotentialMap(const CoordMap& _coord, const xy<double>& _target)

     : coord(_coord), target(_target) {}

   double operator[](const Key& node) const {

     return std::sqrt((coord[node].x - target.x) * (coord[node].x - target.x) + 

 		     (coord[node].y - target.y) * (coord[node].y - target.y));

   }

 private:

   xy<double> target;

   const CoordMap& coord;

 };

 template <typename Graph, typename LengthMap, typename PotentialMap>

 class ReducedLengthMap {

 public:

   typedef double Value;

   typedef typename LengthMap::Key Key;

   ReducedLengthMap(const Graph& _graph, const LengthMap& _length, 

 		   const PotentialMap& _pot) 

     : graph(_graph), length(_length), pot(_pot) {}

   Value operator[](const Key& edge) const {

     return length[edge] - (pot[graph.source(edge)] - pot[graph.target(edge)]);

   }

 private:

   const Graph& graph;

   const LengthMap& length;

   const PotentialMap& pot;

 };

 int main() {

   typedef SmartGraph Graph;

   typedef Graph::Edge Edge;

   typedef Graph::Node Node;

   typedef Graph::EdgeIt EdgeIt;

   typedef Graph::NodeIt NodeIt;

   typedef Graph::EdgeMap<double> LengthMap;

   typedef Graph::NodeMap<xy<double> > CoordMap;

   SmartGraph graph;

   GraphReader<Graph> reader(std::cin, graph);

   CoordMap coord(graph);

   XMap<CoordMap> xcoord = xMap(coord);

   reader.addNodeMap("coordinates_x", xcoord);

   YMap<CoordMap> ycoord = yMap(coord);

   reader.addNodeMap("coordinates_y", ycoord);

   LengthMap length(graph);

   reader.addEdgeMap("length", length);

   Node source, target;

   reader.addNode("source", source);

   reader.addNode("target", target);

   reader.run();

   {

     Timer timer;

     Dijkstra<Graph, LengthMap> dijkstra(graph, length);

     dijkstra.init();

     dijkstra.addSource(source);

     dijkstra.start(target);

     std::cout << dijkstra.dist(target) << std::endl;

     std::cout << timer << std::endl;

   }

   {

     Timer timer;

     typedef PotentialMap<CoordMap> Potential;

     Potential potential(coord, coord[target]);

     typedef ReducedLengthMap<Graph, LengthMap, Potential> ReducedLength;

     ReducedLength reduced(graph, length, potential);

     Dijkstra<Graph, ReducedLength> dijkstra(graph, reduced);

     dijkstra.init();

     dijkstra.addSource(source);

     dijkstra.start(target);

     std::cout << dijkstra.dist(target) + potential[source] << std::endl;

     std::cout << timer << std::endl;

   }

   return 0;

 }