Template for weight in AStar

29 files changed, 356 insertions, 175 deletions

diff --git a/generator/routing_index_generator.cpp b/generator/routing_index_generator.cpp
index 9a52353b7d..a96df99732 100644
--- a/generator/routing_index_generator.cpp
+++ b/generator/routing_index_generator.cpp
@@ -140,6 +140,7 @@ public:
   // AStarAlgorithm types aliases:
   using TVertexType = Segment;
   using TEdgeType = SegmentEdge;
+  using TWeightType = RouteWeight;
 
   explicit DijkstraWrapper(IndexGraph & graph) : m_graph(graph) {}
 
@@ -155,9 +156,9 @@ public:
     m_graph.GetEdgeList(vertex, false /* isOutgoing */, edges);
   }
 
-  double HeuristicCostEstimate(TVertexType const & /* from */, TVertexType const & /* to */)
+  TWeightType HeuristicCostEstimate(TVertexType const & /* from */, TVertexType const & /* to */)
   {
-    return 0.0;
+    return GetAStarWeightZero<TWeightType>();
   }
 
 private:
@@ -177,10 +178,10 @@ bool RegionsContain(vector<m2::RegionD> const & regions, m2::PointD const & poin
 
 // Calculate distance from the starting border point to the transition along the border.
 // It could be measured clockwise or counterclockwise, direction doesn't matter.
-double CalcDistanceAlongTheBorders(vector<m2::RegionD> const & borders,
-                                   CrossMwmConnectorSerializer::Transition const & transition)
+RouteWeight CalcDistanceAlongTheBorders(vector<m2::RegionD> const & borders,
+                                        CrossMwmConnectorSerializer::Transition const & transition)
 {
-  double distance = 0.0;
+  RouteWeight distance = GetAStarWeightZero<RouteWeight>();
 
   for (m2::RegionD const & region : borders)
   {
@@ -194,11 +195,11 @@ double CalcDistanceAlongTheBorders(vector<m2::RegionD> const & borders,
       if (m2::RegionD::IsIntersect(transition.GetBackPoint(), transition.GetFrontPoint(), *prev,
                                    curr, intersection))
       {
-        distance += prev->Length(intersection);
+        distance += RouteWeight(prev->Length(intersection));
         return distance;
       }
 
-      distance += prev->Length(curr);
+      distance += RouteWeight(prev->Length(curr));
       prev = &curr;
     }
   }
@@ -288,7 +289,7 @@ void FillWeights(string const & path, string const & mwmFile, string const & cou
   MwmValue mwmValue(LocalCountryFile(path, platform::CountryFile(country), 0 /* version */));
   DeserializeIndexGraph(mwmValue, kCarMask, graph);
 
-  map<Segment, map<Segment, double>> weights;
+  map<Segment, map<Segment, RouteWeight>> weights;
   auto const numEnters = connector.GetEnters().size();
   size_t foundCount = 0;
   size_t notFoundCount = 0;
@@ -323,11 +324,11 @@ void FillWeights(string const & path, string const & mwmFile, string const & cou
   connector.FillWeights([&](Segment const & enter, Segment const & exit) {
     auto it0 = weights.find(enter);
     if (it0 == weights.end())
-      return CrossMwmConnector::kNoRoute;
+      return RouteWeight(CrossMwmConnector::kNoRoute);
 
     auto it1 = it0->second.find(exit);
     if (it1 == it0->second.end())
-      return CrossMwmConnector::kNoRoute;
+      return RouteWeight(CrossMwmConnector::kNoRoute);
 
     return it1->second;
   });
diff --git a/routing/CMakeLists.txt b/routing/CMakeLists.txt
index e5d0091dcc..3a3abab457 100644
--- a/routing/CMakeLists.txt
+++ b/routing/CMakeLists.txt
@@ -12,6 +12,7 @@ set(
   async_router.cpp
   async_router.hpp
   base/astar_algorithm.hpp
+  base/astar_weight.hpp
   base/followed_polyline.cpp
   base/followed_polyline.hpp
   bicycle_directions.cpp
@@ -92,6 +93,8 @@ set(
   route.cpp
   route.hpp
   route_point.hpp
+  route_weight.cpp
+  route_weight.hpp
   router.cpp
   router.hpp
   router_delegate.cpp
diff --git a/routing/base/astar_algorithm.hpp b/routing/base/astar_algorithm.hpp
index ebd27b4085..072ae2e5a3 100644
--- a/routing/base/astar_algorithm.hpp
+++ b/routing/base/astar_algorithm.hpp
@@ -1,30 +1,31 @@
 #pragma once
 
+#include "routing/base/astar_weight.hpp"
+
 #include "base/assert.hpp"
 #include "base/cancellable.hpp"
-#include "std/algorithm.hpp"
-#include "std/functional.hpp"
-#include "std/iostream.hpp"
-#include "std/limits.hpp"
-#include "std/map.hpp"
-#include "std/queue.hpp"
-#include "std/vector.hpp"
+
+#include <algorithm>
+#include <iostream>
+#include <map>
+#include <queue>
+#include <vector>
 
 namespace routing
 {
 
-template <typename TVertexType>
+template <typename TVertexType, typename TWeightType>
 struct RoutingResult
 {
-  vector<TVertexType> path;
-  double distance;
+  std::vector<TVertexType> path;
+  TWeightType distance;
 
-  RoutingResult() : distance(0) {}
+  RoutingResult() : distance(GetAStarWeightZero<TWeightType>()) {}
 
   void Clear()
   {
     path.clear();
-    distance = 0;
+    distance = GetAStarWeightZero<TWeightType>();
   }
 };
 
@@ -35,6 +36,7 @@ public:
   using TGraphType = TGraph;
   using TVertexType = typename TGraphType::TVertexType;
   using TEdgeType = typename TGraphType::TEdgeType;
+  using TWeightType = typename TGraphType::TWeightType;
 
   enum class Result
   {
@@ -43,7 +45,7 @@ public:
     Cancelled
   };
 
-  friend ostream & operator<<(ostream & os, Result const & result)
+  friend std::ostream & operator<<(std::ostream & os, Result const & result)
   {
     switch (result)
     {
@@ -76,7 +78,7 @@ public:
       return m_distanceMap.find(vertex) != m_distanceMap.cend();
     }
 
-    double GetDistance(TVertexType const & vertex) const
+    TWeightType GetDistance(TVertexType const & vertex) const
     {
       auto const & it = m_distanceMap.find(vertex);
       if (it == m_distanceMap.cend())
@@ -85,7 +87,7 @@ public:
       return it->second;
     }
 
-    void SetDistance(TVertexType const & vertex, double distance)
+    void SetDistance(TVertexType const & vertex, TWeightType const & distance)
     {
       m_distanceMap[vertex] = distance;
     }
@@ -95,11 +97,11 @@ public:
       m_parents[parent] = child;
     }
 
-    void ReconstructPath(TVertexType const & v, vector<TVertexType> & path) const;
+    void ReconstructPath(TVertexType const & v, std::vector<TVertexType> & path) const;
 
   private:
-    map<TVertexType, double> m_distanceMap;
-    map<TVertexType, TVertexType> m_parents;
+    std::map<TVertexType, TWeightType> m_distanceMap;
+    std::map<TVertexType, TVertexType> m_parents;
   };
 
   // VisitVertex returns true: wave will continue
@@ -114,30 +116,31 @@ public:
                      VisitVertex && visitVertex, Context & context) const;
 
   Result FindPath(TGraphType & graph, TVertexType const & startVertex,
-                  TVertexType const & finalVertex, RoutingResult<TVertexType> & result,
+                  TVertexType const & finalVertex, RoutingResult<TVertexType, TWeightType> & result,
                   my::Cancellable const & cancellable = my::Cancellable(),
                   TOnVisitedVertexCallback onVisitedVertexCallback = nullptr) const;
 
   Result FindPathBidirectional(TGraphType & graph,
                                TVertexType const & startVertex, TVertexType const & finalVertex,
-                               RoutingResult<TVertexType> & result,
+                               RoutingResult<TVertexType, TWeightType> & result,
                                my::Cancellable const & cancellable = my::Cancellable(),
                                TOnVisitedVertexCallback onVisitedVertexCallback = nullptr) const;
 
   // Adjust route to the previous one.
   // adjustLimit - distance limit for wave propagation, measured in same units as graph edges length.
   typename AStarAlgorithm<TGraph>::Result AdjustRoute(
-      TGraphType & graph, TVertexType const & startVertex, vector<TEdgeType> const & prevRoute,
-      double adjustLimit, RoutingResult<TVertexType> & result, my::Cancellable const & cancellable,
-      TOnVisitedVertexCallback onVisitedVertexCallback) const;
+      TGraphType & graph, TVertexType const & startVertex, std::vector<TEdgeType> const & prevRoute,
+      TWeightType const & adjustLimit, RoutingResult<TVertexType, TWeightType> & result,
+      my::Cancellable const & cancellable, TOnVisitedVertexCallback onVisitedVertexCallback) const;
 
 private:
   // Periodicity of switching a wave of bidirectional algorithm.
   static uint32_t constexpr kQueueSwitchPeriod = 128;
 
   // Precision of comparison weights.
-  static double constexpr kEpsilon = 1e-6;
-  static double constexpr kInfiniteDistance = numeric_limits<double>::max();
+  static TWeightType constexpr kEpsilon = GetAStarWeightEpsilon<TWeightType>();
+  static TWeightType constexpr kZeroDistance = GetAStarWeightZero<TWeightType>();
+  static TWeightType constexpr kInfiniteDistance = GetAStarWeightMax<TWeightType>();
 
   class PeriodicPollCancellable final
   {
@@ -160,12 +163,15 @@ private:
   // comment for FindPath for more information.
   struct State
   {
-    State(TVertexType const & vertex, double distance) : vertex(vertex), distance(distance) {}
+    State(TVertexType const & vertex, TWeightType const & distance)
+      : vertex(vertex), distance(distance)
+    {
+    }
 
     inline bool operator>(State const & rhs) const { return distance > rhs.distance; }
 
     TVertexType vertex;
-    double distance;
+    TWeightType distance;
   };
 
   // BidirectionalStepContext keeps all the information that is needed to
@@ -183,7 +189,7 @@ private:
       pS = ConsistentHeuristic(bestVertex);
     }
 
-    double TopDistance() const
+    TWeightType TopDistance() const
     {
       ASSERT(!queue.empty(), ());
       return bestDistance.at(queue.top().vertex);
@@ -192,10 +198,10 @@ private:
     // p_f(v) = 0.5*(π_f(v) - π_r(v)) + 0.5*π_r(t)
     // p_r(v) = 0.5*(π_r(v) - π_f(v)) + 0.5*π_f(s)
     // p_r(v) + p_f(v) = const. Note: this condition is called consistence.
-    double ConsistentHeuristic(TVertexType const & v) const
+    TWeightType ConsistentHeuristic(TVertexType const & v) const
     {
-      double const piF = graph.HeuristicCostEstimate(v, finalVertex);
-      double const piR = graph.HeuristicCostEstimate(v, startVertex);
+      auto const piF = graph.HeuristicCostEstimate(v, finalVertex);
+      auto const piR = graph.HeuristicCostEstimate(v, startVertex);
       if (forward)
       {
         /// @todo careful: with this "return" here and below in the Backward case
@@ -210,7 +216,7 @@ private:
       }
     }
 
-    void GetAdjacencyList(TVertexType const & v, vector<TEdgeType> & adj)
+    void GetAdjacencyList(TVertexType const & v, std::vector<TEdgeType> & adj)
     {
       if (forward)
         graph.GetOutgoingEdgesList(v, adj);
@@ -222,26 +228,34 @@ private:
     TVertexType const & startVertex;
     TVertexType const & finalVertex;
     TGraph & graph;
-    double const m_piRT;
-    double const m_piFS;
+    TWeightType const m_piRT;
+    TWeightType const m_piFS;
 
-    priority_queue<State, vector<State>, greater<State>> queue;
-    map<TVertexType, double> bestDistance;
-    map<TVertexType, TVertexType> parent;
+    std::priority_queue<State, std::vector<State>, std::greater<State>> queue;
+    std::map<TVertexType, TWeightType> bestDistance;
+    std::map<TVertexType, TVertexType> parent;
     TVertexType bestVertex;
 
-    double pS;
+    TWeightType pS;
   };
 
-  static void ReconstructPath(TVertexType const & v, map<TVertexType, TVertexType> const & parent,
-                              vector<TVertexType> & path);
+  static void ReconstructPath(TVertexType const & v,
+                              std::map<TVertexType, TVertexType> const & parent,
+                              std::vector<TVertexType> & path);
   static void ReconstructPathBidirectional(TVertexType const & v, TVertexType const & w,
-                                           map<TVertexType, TVertexType> const & parentV,
-                                           map<TVertexType, TVertexType> const & parentW,
-                                           vector<TVertexType> & path);
+                                           std::map<TVertexType, TVertexType> const & parentV,
+                                           std::map<TVertexType, TVertexType> const & parentW,
+                                           std::vector<TVertexType> & path);
 };
 
 template <typename TGraph>
+constexpr typename TGraph::TWeightType AStarAlgorithm<TGraph>::kEpsilon;
+template <typename TGraph>
+constexpr typename TGraph::TWeightType AStarAlgorithm<TGraph>::kInfiniteDistance;
+template <typename TGraph>
+constexpr typename TGraph::TWeightType AStarAlgorithm<TGraph>::kZeroDistance;
+
+template <typename TGraph>
 template <typename VisitVertex, typename AdjustEdgeWeight>
 void AStarAlgorithm<TGraph>::PropagateWave(TGraphType & graph, TVertexType const & startVertex,
                                            VisitVertex && visitVertex,
@@ -250,12 +264,12 @@ void AStarAlgorithm<TGraph>::PropagateWave(TGraphType & graph, TVertexType const
 {
   context.Clear();
 
-  priority_queue<State, vector<State>, greater<State>> queue;
+  std::priority_queue<State, std::vector<State>, std::greater<State>> queue;
 
-  context.SetDistance(startVertex, 0.0);
-  queue.push(State(startVertex, 0.0));
+  context.SetDistance(startVertex, kZeroDistance);
+  queue.push(State(startVertex, kZeroDistance));
 
-  vector<TEdgeType> adj;
+  std::vector<TEdgeType> adj;
 
   while (!queue.empty())
   {
@@ -271,12 +285,12 @@ void AStarAlgorithm<TGraph>::PropagateWave(TGraphType & graph, TVertexType const
     graph.GetOutgoingEdgesList(stateV.vertex, adj);
     for (auto const & edge : adj)
     {
-      State stateW(edge.GetTarget(), 0.0);
+      State stateW(edge.GetTarget(), kZeroDistance);
       if (stateV.vertex == stateW.vertex)
         continue;
 
-      double const edgeWeight = adjustEdgeWeight(stateV.vertex, edge);
-      double const newReducedDist = stateV.distance + edgeWeight;
+      auto const edgeWeight = adjustEdgeWeight(stateV.vertex, edge);
+      auto const newReducedDist = stateV.distance + edgeWeight;
 
       if (newReducedDist >= context.GetDistance(stateW.vertex) - kEpsilon)
         continue;
@@ -315,7 +329,7 @@ void AStarAlgorithm<TGraph>::PropagateWave(TGraphType & graph, TVertexType const
 template <typename TGraph>
 typename AStarAlgorithm<TGraph>::Result AStarAlgorithm<TGraph>::FindPath(
     TGraphType & graph, TVertexType const & startVertex, TVertexType const & finalVertex,
-    RoutingResult<TVertexType> & result, my::Cancellable const & cancellable,
+    RoutingResult<TVertexType, TWeightType> & result, my::Cancellable const & cancellable,
     TOnVisitedVertexCallback onVisitedVertexCallback) const
 {
   result.Clear();
@@ -345,13 +359,13 @@ typename AStarAlgorithm<TGraph>::Result AStarAlgorithm<TGraph>::FindPath(
   };
 
   auto adjustEdgeWeight = [&](TVertexType const & vertex, TEdgeType const & edge) {
-    double const len = edge.GetWeight();
-    double const piV = graph.HeuristicCostEstimate(vertex, finalVertex);
-    double const piW = graph.HeuristicCostEstimate(edge.GetTarget(), finalVertex);
-    double const reducedLen = len + piW - piV;
+    auto const len = edge.GetWeight();
+    auto const piV = graph.HeuristicCostEstimate(vertex, finalVertex);
+    auto const piW = graph.HeuristicCostEstimate(edge.GetTarget(), finalVertex);
+    auto const reducedLen = len + piW - piV;
 
     CHECK(reducedLen >= -kEpsilon, ("Invariant violated:", reducedLen, "<", -kEpsilon));
-    return max(reducedLen, 0.0);
+    return std::max(reducedLen, kZeroDistance);
   };
 
   PropagateWave(graph, startVertex, visitVertex, adjustEdgeWeight, context);
@@ -370,7 +384,7 @@ template <typename TGraph>
 typename AStarAlgorithm<TGraph>::Result AStarAlgorithm<TGraph>::FindPathBidirectional(
     TGraphType & graph,
     TVertexType const & startVertex, TVertexType const & finalVertex,
-    RoutingResult<TVertexType> & result,
+    RoutingResult<TVertexType, TWeightType> & result,
     my::Cancellable const & cancellable,
     TOnVisitedVertexCallback onVisitedVertexCallback) const
 {
@@ -381,14 +395,14 @@ typename AStarAlgorithm<TGraph>::Result AStarAlgorithm<TGraph>::FindPathBidirect
   BidirectionalStepContext backward(false /* forward */, startVertex, finalVertex, graph);
 
   bool foundAnyPath = false;
-  double bestPathReducedLength = 0.0;
-  double bestPathRealLength = 0.0;
+  auto bestPathReducedLength = kZeroDistance;
+  auto bestPathRealLength = kZeroDistance;
 
-  forward.bestDistance[startVertex] = 0.0;
-  forward.queue.push(State(startVertex, 0.0 /* distance */));
+  forward.bestDistance[startVertex] = kZeroDistance;
+  forward.queue.push(State(startVertex, kZeroDistance));
 
-  backward.bestDistance[finalVertex] = 0.0;
-  backward.queue.push(State(finalVertex, 0.0 /* distance */));
+  backward.bestDistance[finalVertex] = kZeroDistance;
+  backward.queue.push(State(finalVertex, kZeroDistance));
 
   // To use the search code both for backward and forward directions
   // we keep the pointers to everything related to the search in the
@@ -397,7 +411,7 @@ typename AStarAlgorithm<TGraph>::Result AStarAlgorithm<TGraph>::FindPathBidirect
   BidirectionalStepContext * cur = &forward;
   BidirectionalStepContext * nxt = &backward;
 
-  vector<TEdgeType> adj;
+  std::vector<TEdgeType> adj;
 
   // It is not necessary to check emptiness for both queues here
   // because if we have not found a path by the time one of the
@@ -413,12 +427,12 @@ typename AStarAlgorithm<TGraph>::Result AStarAlgorithm<TGraph>::FindPathBidirect
       return Result::Cancelled;
 
     if (steps % kQueueSwitchPeriod == 0)
-      swap(cur, nxt);
+      std::swap(cur, nxt);
 
     if (foundAnyPath)
     {
-      double const curTop = cur->TopDistance();
-      double const nxtTop = nxt->TopDistance();
+      auto const curTop = cur->TopDistance();
+      auto const nxtTop = nxt->TopDistance();
 
       // The intuition behind this is that we cannot obtain a path shorter
       // than the left side of the inequality because that is how any path we find
@@ -454,17 +468,17 @@ typename AStarAlgorithm<TGraph>::Result AStarAlgorithm<TGraph>::FindPathBidirect
     cur->GetAdjacencyList(stateV.vertex, adj);
     for (auto const & edge : adj)
     {
-      State stateW(edge.GetTarget(), 0.0);
+      State stateW(edge.GetTarget(), kZeroDistance);
       if (stateV.vertex == stateW.vertex)
         continue;
 
-      double const len = edge.GetWeight();
-      double const pV = cur->ConsistentHeuristic(stateV.vertex);
-      double const pW = cur->ConsistentHeuristic(stateW.vertex);
-      double const reducedLen = len + pW - pV;
+      auto const len = edge.GetWeight();
+      auto const pV = cur->ConsistentHeuristic(stateV.vertex);
+      auto const pW = cur->ConsistentHeuristic(stateW.vertex);
+      auto const reducedLen = len + pW - pV;
 
       CHECK(reducedLen >= -kEpsilon, ("Invariant violated:", reducedLen, "<", -kEpsilon));
-      double const newReducedDist = stateV.distance + max(reducedLen, 0.0);
+      auto const newReducedDist = stateV.distance + std::max(reducedLen, kZeroDistance);
 
       auto const itCur = cur->bestDistance.find(stateW.vertex);
       if (itCur != cur->bestDistance.end() && newReducedDist >= itCur->second - kEpsilon)
@@ -473,10 +487,10 @@ typename AStarAlgorithm<TGraph>::Result AStarAlgorithm<TGraph>::FindPathBidirect
       auto const itNxt = nxt->bestDistance.find(stateW.vertex);
       if (itNxt != nxt->bestDistance.end())
       {
-        double const distW = itNxt->second;
+        auto const distW = itNxt->second;
         // Reduced length that the path we've just found has in the original graph:
         // find the reduced length of the path's parts in the reduced forward and backward graphs.
-        double const curPathReducedLength = newReducedDist + distW;
+        auto const curPathReducedLength = newReducedDist + distW;
         // No epsilon here: it is ok to overshoot slightly.
         if (!foundAnyPath || bestPathReducedLength > curPathReducedLength)
         {
@@ -504,9 +518,9 @@ typename AStarAlgorithm<TGraph>::Result AStarAlgorithm<TGraph>::FindPathBidirect
 
 template <typename TGraph>
 typename AStarAlgorithm<TGraph>::Result AStarAlgorithm<TGraph>::AdjustRoute(
-    TGraphType & graph, TVertexType const & startVertex, vector<TEdgeType> const & prevRoute,
-    double adjustLimit, RoutingResult<TVertexType> & result, my::Cancellable const & cancellable,
-    TOnVisitedVertexCallback onVisitedVertexCallback) const
+    TGraphType & graph, TVertexType const & startVertex, std::vector<TEdgeType> const & prevRoute,
+    TWeightType const & adjustLimit, RoutingResult<TVertexType, TWeightType> & result,
+    my::Cancellable const & cancellable, TOnVisitedVertexCallback onVisitedVertexCallback) const
 {
   CHECK(!prevRoute.empty(), ());
 
@@ -515,11 +529,11 @@ typename AStarAlgorithm<TGraph>::Result AStarAlgorithm<TGraph>::AdjustRoute(
     onVisitedVertexCallback = [](TVertexType const &, TVertexType const &) {};
 
   bool wasCancelled = false;
-  double minDistance = kInfiniteDistance;
+  auto minDistance = kInfiniteDistance;
   TVertexType returnVertex;
 
-  map<TVertexType, double> remainingDistances;
-  double remainingDistance = 0.0;
+  std::map<TVertexType, TWeightType> remainingDistances;
+  auto remainingDistance = kZeroDistance;
 
   for (auto it = prevRoute.crbegin(); it != prevRoute.crend(); ++it)
   {
@@ -547,7 +561,7 @@ typename AStarAlgorithm<TGraph>::Result AStarAlgorithm<TGraph>::AdjustRoute(
     auto it = remainingDistances.find(vertex);
     if (it != remainingDistances.cend())
     {
-      double const fullDistance = distance + it->second;
+      auto const fullDistance = distance + it->second;
       if (fullDistance < minDistance)
       {
         minDistance = fullDistance;
@@ -593,8 +607,8 @@ typename AStarAlgorithm<TGraph>::Result AStarAlgorithm<TGraph>::AdjustRoute(
 // static
 template <typename TGraph>
 void AStarAlgorithm<TGraph>::ReconstructPath(TVertexType const & v,
-                                             map<TVertexType, TVertexType> const & parent,
-                                             vector<TVertexType> & path)
+                                             std::map<TVertexType, TVertexType> const & parent,
+                                             std::vector<TVertexType> & path)
 {
   path.clear();
   TVertexType cur = v;
@@ -612,12 +626,13 @@ void AStarAlgorithm<TGraph>::ReconstructPath(TVertexType const & v,
 // static
 template <typename TGraph>
 void AStarAlgorithm<TGraph>::ReconstructPathBidirectional(
-    TVertexType const & v, TVertexType const & w, map<TVertexType, TVertexType> const & parentV,
-    map<TVertexType, TVertexType> const & parentW, vector<TVertexType> & path)
+    TVertexType const & v, TVertexType const & w,
+    std::map<TVertexType, TVertexType> const & parentV,
+    std::map<TVertexType, TVertexType> const & parentW, std::vector<TVertexType> & path)
 {
-  vector<TVertexType> pathV;
+  std::vector<TVertexType> pathV;
   ReconstructPath(v, parentV, pathV);
-  vector<TVertexType> pathW;
+  std::vector<TVertexType> pathW;
   ReconstructPath(w, parentW, pathW);
   path.clear();
   path.reserve(pathV.size() + pathW.size());
@@ -627,7 +642,7 @@ void AStarAlgorithm<TGraph>::ReconstructPathBidirectional(
 
 template <typename TGraph>
 void AStarAlgorithm<TGraph>::Context::ReconstructPath(TVertexType const & v,
-                                                      vector<TVertexType> & path) const
+                                                      std::vector<TVertexType> & path) const
 {
   AStarAlgorithm<TGraph>::ReconstructPath(v, m_parents, path);
 }
diff --git a/routing/base/astar_weight.hpp b/routing/base/astar_weight.hpp
new file mode 100644
index 0000000000..2d8c725462
--- /dev/null
+++ b/routing/base/astar_weight.hpp
@@ -0,0 +1,35 @@
+#pragma once
+
+#include <limits>
+
+namespace routing
+{
+template <typename WeightType>
+constexpr WeightType GetAStarWeightZero();
+
+template <>
+constexpr double GetAStarWeightZero<double>()
+{
+  return 0.0;
+}
+
+// Precision of comparison weights.
+template <typename WeightType>
+constexpr WeightType GetAStarWeightEpsilon();
+
+template <>
+constexpr double GetAStarWeightEpsilon<double>()
+{
+  return 1e-6;
+}
+
+template <typename WeightType>
+constexpr WeightType GetAStarWeightMax();
+
+template <>
+constexpr double GetAStarWeightMax<double>()
+{
+  return std::numeric_limits<double>::max();
+}
+
+}  // namespace routing
diff --git a/routing/cross_mwm_connector.cpp b/routing/cross_mwm_connector.cpp
index 23bcc316a9..64297d37a0 100644
--- a/routing/cross_mwm_connector.cpp
+++ b/routing/cross_mwm_connector.cpp
@@ -150,7 +150,7 @@ void CrossMwmConnector::AddEdge(Segment const & segment, Weight weight,
                                 std::vector<SegmentEdge> & edges) const
 {
   if (weight != static_cast<Weight>(kNoRoute))
-    edges.emplace_back(segment, static_cast<double>(weight));
+    edges.emplace_back(segment, RouteWeight(static_cast<double>(weight)));
 }
 
 CrossMwmConnector::Transition const & CrossMwmConnector::GetTransition(
diff --git a/routing/cross_mwm_connector.hpp b/routing/cross_mwm_connector.hpp
index ad42bba97f..1b5d49ac72 100644
--- a/routing/cross_mwm_connector.hpp
+++ b/routing/cross_mwm_connector.hpp
@@ -62,9 +62,9 @@ public:
     {
       for (Segment const & exit : m_exits)
       {
-        double const weight = calcWeight(enter, exit);
+        RouteWeight const weight = calcWeight(enter, exit);
         // Edges weights should be >= astar heuristic, so use std::ceil.
-        m_weights.push_back(static_cast<Weight>(std::ceil(weight)));
+        m_weights.push_back(static_cast<Weight>(std::ceil(weight.GetWeight())));
       }
     }
   }
diff --git a/routing/cross_mwm_osrm_graph.cpp b/routing/cross_mwm_osrm_graph.cpp
index 4edc11bcb2..58c7aae429 100644
--- a/routing/cross_mwm_osrm_graph.cpp
+++ b/routing/cross_mwm_osrm_graph.cpp
@@ -103,8 +103,8 @@ void AddSegmentEdge(NumMwmIds const & numMwmIds, OsrmFtSegMapping const & segMap
   double constexpr kAstarHeuristicFactor = 100000;
   //// Osrm multiplies seconds to 10, so we need to divide it back.
   double constexpr kOSRMWeightToSecondsMultiplier = 0.1;
-  edges.emplace_back(segment,
-                     osrmEdge.GetWeight() * kOSRMWeightToSecondsMultiplier * kAstarHeuristicFactor);
+  edges.emplace_back(segment, RouteWeight(osrmEdge.GetWeight() * kOSRMWeightToSecondsMultiplier *
+                                          kAstarHeuristicFactor));
 }
 }  // namespace
 
diff --git a/routing/cross_mwm_road_graph.hpp b/routing/cross_mwm_road_graph.hpp
index 058e55450d..271fddc943 100644
--- a/routing/cross_mwm_road_graph.hpp
+++ b/routing/cross_mwm_road_graph.hpp
@@ -126,6 +126,7 @@ public:
   using TCachingKey = pair<TWrittenNodeId, Index::MwmId>;
   using TVertexType = BorderCross;
   using TEdgeType = CrossWeightedEdge;
+  using TWeightType = double;
 
   struct Hash
   {
diff --git a/routing/cross_mwm_router.cpp b/routing/cross_mwm_router.cpp
index 1523a84b4d..df4e6a15c6 100644
--- a/routing/cross_mwm_router.cpp
+++ b/routing/cross_mwm_router.cpp
@@ -13,7 +13,7 @@ namespace
 /// Function to run AStar Algorithm from the base.
 IRouter::ResultCode CalculateRoute(BorderCross const & startPos, BorderCross const & finalPos,
                                    CrossMwmRoadGraph & roadGraph, RouterDelegate const & delegate,
-                                   RoutingResult<BorderCross> & route)
+                                   RoutingResult<BorderCross, double /* WeightType */> & route)
 {
   using TAlgorithm = AStarAlgorithm<CrossMwmRoadGraph>;
 
@@ -90,7 +90,7 @@ IRouter::ResultCode CalculateCrossMwmPath(TRoutingNodes const & startGraphNodes,
     return IRouter::EndPointNotFound;
 
   // Finding path through maps.
-  RoutingResult<BorderCross> tempRoad;
+  RoutingResult<BorderCross, double /* WeightType */> tempRoad;
   code = CalculateRoute({startNode, startNode}, {finalNode, finalNode}, roadGraph, delegate, tempRoad);
   cost = tempRoad.distance;
   if (code != IRouter::NoError)
diff --git a/routing/index_graph.cpp b/routing/index_graph.cpp
index bc9ec4a76f..27f91c479e 100644
--- a/routing/index_graph.cpp
+++ b/routing/index_graph.cpp
@@ -109,14 +109,16 @@ void IndexGraph::GetIngoingEdgesList(Segment const & segment, vector<SegmentEdge
   GetEdgeList(segment, false /* isOutgoing */, edges);
 }
 
-double IndexGraph::HeuristicCostEstimate(Segment const & from, Segment const & to)
+RouteWeight IndexGraph::HeuristicCostEstimate(Segment const & from, Segment const & to)
 {
-  return m_estimator->CalcHeuristic(GetPoint(from, true /* front */), GetPoint(to, true /* front */));
+  return RouteWeight(
+      m_estimator->CalcHeuristic(GetPoint(from, true /* front */), GetPoint(to, true /* front */)));
 }
 
-double IndexGraph::CalcSegmentWeight(Segment const & segment)
+RouteWeight IndexGraph::CalcSegmentWeight(Segment const & segment)
 {
-  return m_estimator->CalcSegmentWeight(segment, m_geometry.GetRoad(segment.GetFeatureId()));
+  return RouteWeight(
+      m_estimator->CalcSegmentWeight(segment, m_geometry.GetRoad(segment.GetFeatureId())));
 }
 
 void IndexGraph::GetNeighboringEdges(Segment const & from, RoadPoint const & rp, bool isOutgoing,
@@ -161,16 +163,16 @@ void IndexGraph::GetNeighboringEdge(Segment const & from, Segment const & to, bo
   if (m_roadAccess.GetSegmentType(to) != RoadAccess::Type::Yes)
     return;
 
-  double const weight = CalcSegmentWeight(isOutgoing ? to : from) +
-                        GetPenalties(isOutgoing ? from : to, isOutgoing ? to : from);
+  RouteWeight const weight = CalcSegmentWeight(isOutgoing ? to : from) +
+                             GetPenalties(isOutgoing ? from : to, isOutgoing ? to : from);
   edges.emplace_back(to, weight);
 }
 
-double IndexGraph::GetPenalties(Segment const & u, Segment const & v) const
+RouteWeight IndexGraph::GetPenalties(Segment const & u, Segment const & v) const
 {
   if (IsUTurn(u, v))
-    return m_estimator->GetUTurnPenalty();
+    return RouteWeight(m_estimator->GetUTurnPenalty());
 
-  return 0.0;
+  return RouteWeight(0.0);
 }
 }  // namespace routing
diff --git a/routing/index_graph.hpp b/routing/index_graph.hpp
index 6cb01899bd..ecf171aa0c 100644
--- a/routing/index_graph.hpp
+++ b/routing/index_graph.hpp
@@ -26,6 +26,7 @@ public:
   // AStarAlgorithm types aliases:
   using TVertexType = Segment;
   using TEdgeType = SegmentEdge;
+  using TWeightType = RouteWeight;
 
   IndexGraph() = default;
   explicit IndexGraph(unique_ptr<GeometryLoader> loader, shared_ptr<EdgeEstimator> estimator);
@@ -52,7 +53,7 @@ public:
   // Interface for AStarAlgorithm:
   void GetOutgoingEdgesList(Segment const & segment, vector<SegmentEdge> & edges);
   void GetIngoingEdgesList(Segment const & segment, vector<SegmentEdge> & edges);
-  double HeuristicCostEstimate(Segment const & from, Segment const & to);
+  RouteWeight HeuristicCostEstimate(Segment const & from, Segment const & to);
 
   void PushFromSerializer(Joint::Id jointId, RoadPoint const & rp)
   {
@@ -72,12 +73,12 @@ public:
   }
 
 private:
-  double CalcSegmentWeight(Segment const & segment);
+  RouteWeight CalcSegmentWeight(Segment const & segment);
   void GetNeighboringEdges(Segment const & from, RoadPoint const & rp, bool isOutgoing,
                            vector<SegmentEdge> & edges);
   void GetNeighboringEdge(Segment const & from, Segment const & to, bool isOutgoing,
                           vector<SegmentEdge> & edges);
-  double GetPenalties(Segment const & u, Segment const & v) const;
+  RouteWeight GetPenalties(Segment const & u, Segment const & v) const;
   m2::PointD const & GetPoint(Segment const & segment, bool front)
   {
     return GetGeometry().GetRoad(segment.GetFeatureId()).GetPoint(segment.GetPointId(front));
diff --git a/routing/index_graph_starter.cpp b/routing/index_graph_starter.cpp
index 27270a4af9..ed2fc3b63f 100644
--- a/routing/index_graph_starter.cpp
+++ b/routing/index_graph_starter.cpp
@@ -141,7 +141,7 @@ void IndexGraphStarter::GetFakeToNormalEdge(FakeVertex const & fakeVertex, bool
 {
   auto const segment = fakeVertex.GetSegmentWithDirection(forward);
   m2::PointD const & pointTo = GetPoint(segment, true /* front */);
-  double const weight = m_graph.GetEstimator().CalcLeapWeight(fakeVertex.GetPoint(), pointTo);
+  RouteWeight const weight(m_graph.GetEstimator().CalcLeapWeight(fakeVertex.GetPoint(), pointTo));
   edges.emplace_back(segment, weight);
 }
 
@@ -155,16 +155,16 @@ void IndexGraphStarter::GetNormalToFakeEdge(Segment const & segment, FakeVertex
   {
     if (m_graph.IsTransition(segment, isOutgoing))
     {
-      edges.emplace_back(fakeSegment,
-                         m_graph.GetEstimator().CalcLeapWeight(pointFrom, fakeVertex.GetPoint()));
+      edges.emplace_back(fakeSegment, RouteWeight(m_graph.GetEstimator().CalcLeapWeight(
+                                          pointFrom, fakeVertex.GetPoint())));
     }
     return;
   }
 
   if (fakeVertex.Fits(segment))
   {
-    edges.emplace_back(fakeSegment,
-                       m_graph.GetEstimator().CalcLeapWeight(pointFrom, fakeVertex.GetPoint()));
+    edges.emplace_back(fakeSegment, RouteWeight(m_graph.GetEstimator().CalcLeapWeight(
+                                        pointFrom, fakeVertex.GetPoint())));
   }
 }
 
@@ -180,8 +180,8 @@ void IndexGraphStarter::ConnectLeapToTransitions(Segment const & segment, bool i
   // So |isEnter| below should be set to true.
   m_graph.ForEachTransition(
       segment.GetMwmId(), !isOutgoing /* isEnter */, [&](Segment const & transition) {
-        edges.emplace_back(transition, m_graph.GetEstimator().CalcLeapWeight(
-          segmentPoint, GetPoint(transition, isOutgoing)));
+        edges.emplace_back(transition, RouteWeight(m_graph.GetEstimator().CalcLeapWeight(
+                                           segmentPoint, GetPoint(transition, isOutgoing))));
       });
 }
 }  // namespace routing
diff --git a/routing/index_graph_starter.hpp b/routing/index_graph_starter.hpp
index 95f7f239b5..8912c1b539 100644
--- a/routing/index_graph_starter.hpp
+++ b/routing/index_graph_starter.hpp
@@ -19,6 +19,7 @@ public:
   // AStarAlgorithm types aliases:
   using TVertexType = IndexGraph::TVertexType;
   using TEdgeType = IndexGraph::TEdgeType;
+  using TWeightType = IndexGraph::TWeightType;
 
   class FakeVertex final
   {
@@ -100,10 +101,10 @@ public:
     GetEdgesList(segment, false /* isOutgoing */, edges);
   }
 
-  double HeuristicCostEstimate(TVertexType const & from, TVertexType const & to)
+  RouteWeight HeuristicCostEstimate(TVertexType const & from, TVertexType const & to)
   {
-    return m_graph.GetEstimator().CalcHeuristic(GetPoint(from, true /* front */),
-                                                GetPoint(to, true /* front */));
+    return RouteWeight(m_graph.GetEstimator().CalcHeuristic(GetPoint(from, true /* front */),
+                                                            GetPoint(to, true /* front */)));
   }
 
   double CalcSegmentWeight(Segment const & segment) const
diff --git a/routing/index_router.cpp b/routing/index_router.cpp
index 4ff89d0083..83e2f7328d 100644
--- a/routing/index_router.cpp
+++ b/routing/index_router.cpp
@@ -108,7 +108,7 @@ IRouter::ResultCode FindPath(
     typename Graph::TVertexType const & start, typename Graph::TVertexType const & finish,
     RouterDelegate const & delegate, Graph & graph,
     typename AStarAlgorithm<Graph>::TOnVisitedVertexCallback const & onVisitedVertexCallback,
-    RoutingResult<typename Graph::TVertexType> & routingResult)
+    RoutingResult<typename Graph::TVertexType, typename Graph::TWeightType> & routingResult)
 {
   AStarAlgorithm<Graph> algorithm;
   return ConvertResult<Graph>(algorithm.FindPathBidirectional(graph, start, finish, routingResult,
@@ -469,7 +469,7 @@ IRouter::ResultCode IndexRouter::CalculateSubroute(Checkpoints const & checkpoin
     delegate.OnPointCheck(pointFrom);
   };
 
-  RoutingResult<Segment> routingResult;
+  RoutingResult<Segment, RouteWeight> routingResult;
   IRouter::ResultCode const result = FindPath(starter.GetStart(), starter.GetFinish(), delegate,
                                               starter, onVisitJunction, routingResult);
   if (result != IRouter::NoError)
@@ -519,7 +519,8 @@ IRouter::ResultCode IndexRouter::AdjustRoute(Checkpoints const & checkpoints,
   for (size_t i = lastSubroute.GetBeginSegmentIdx(); i < lastSubroute.GetEndSegmentIdx(); ++i)
   {
     auto const & step = steps[i];
-    prevEdges.emplace_back(step.GetSegment(), starter.CalcSegmentWeight(step.GetSegment()));
+    prevEdges.emplace_back(step.GetSegment(),
+                           RouteWeight(starter.CalcSegmentWeight(step.GetSegment())));
   }
 
   uint32_t visitCount = 0;
@@ -538,9 +539,10 @@ IRouter::ResultCode IndexRouter::AdjustRoute(Checkpoints const & checkpoints,
   };
 
   AStarAlgorithm<IndexGraphStarter> algorithm;
-  RoutingResult<Segment> result;
-  auto resultCode = ConvertResult<IndexGraphStarter>(algorithm.AdjustRoute(
-      starter, starter.GetStart(), prevEdges, kAdjustLimitSec, result, delegate, onVisitJunction));
+  RoutingResult<Segment, RouteWeight> result;
+  auto resultCode = ConvertResult<IndexGraphStarter>(
+      algorithm.AdjustRoute(starter, starter.GetStart(), prevEdges, RouteWeight(kAdjustLimitSec),
+                            result, delegate, onVisitJunction));
   if (resultCode != IRouter::NoError)
     return resultCode;
 
@@ -672,7 +674,7 @@ IRouter::ResultCode IndexRouter::ProcessLeaps(vector<Segment> const & input,
       ("Different mwm ids for leap enter and exit, i:", i, "size of input:", input.size()));
 
     IRouter::ResultCode result = IRouter::InternalError;
-    RoutingResult<Segment> routingResult;
+    RoutingResult<Segment, RouteWeight> routingResult;
     // In case of leaps from the start to its mwm transition and from finish mwm transition
     // route calculation should be made on the world graph (WorldGraph::Mode::NoLeaps).
     if ((current.GetMwmId() == starter.GetStartVertex().GetMwmId()
diff --git a/routing/road_graph.hpp b/routing/road_graph.hpp
index 4924e22bf2..b84db0e3ac 100644
--- a/routing/road_graph.hpp
+++ b/routing/road_graph.hpp
@@ -131,6 +131,7 @@ public:
   // CheckGraphConnectivity() types aliases:
   using Vertex = Junction;
   using Edge = routing::Edge;
+  using Weight = double;
 
   enum class Mode
   {
diff --git a/routing/road_graph_router.cpp b/routing/road_graph_router.cpp
index 252cfc5769..7615aac1d1 100644
--- a/routing/road_graph_router.cpp
+++ b/routing/road_graph_router.cpp
@@ -193,7 +193,7 @@ IRouter::ResultCode RoadGraphRouter::CalculateRoute(Checkpoints const & checkpoi
   m_roadGraph->AddFakeEdges(startPos, startVicinity);
   m_roadGraph->AddFakeEdges(finalPos, finalVicinity);
 
-  RoutingResult<Junction> result;
+  RoutingResult<Junction, double /* WeightType */> result;
   IRoutingAlgorithm::Result const resultCode =
       m_algorithm->CalculateRoute(*m_roadGraph, startPos, finalPos, delegate, result);
 
diff --git a/routing/route_weight.cpp b/routing/route_weight.cpp
new file mode 100644
index 0000000000..f962b6d345
--- /dev/null
+++ b/routing/route_weight.cpp
@@ -0,0 +1,17 @@
+#include "routing/route_weight.hpp"
+
+using namespace std;
+
+namespace routing
+{
+ostream & operator<<(ostream & os, RouteWeight const & routeWeight)
+{
+  os << routeWeight.GetWeight();
+  return os;
+}
+
+RouteWeight operator*(double lhs, RouteWeight const & rhs)
+{
+  return RouteWeight(lhs * rhs.GetWeight());
+}
+}  // namespace routing
diff --git a/routing/route_weight.hpp b/routing/route_weight.hpp
new file mode 100644
index 0000000000..adebf609bc
--- /dev/null
+++ b/routing/route_weight.hpp
@@ -0,0 +1,73 @@
+#pragma once
+
+#include "routing/base/astar_weight.hpp"
+
+#include <iostream>
+#include <limits>
+
+namespace routing
+{
+class RouteWeight final
+{
+public:
+  RouteWeight() = default;
+
+  constexpr explicit RouteWeight(double weight) : m_weight(weight) {}
+
+  double GetWeight() const { return m_weight; }
+
+  bool operator<(RouteWeight const & rhs) const { return m_weight < rhs.m_weight; }
+
+  bool operator==(RouteWeight const & rhs) const { return !((*this) < rhs) && !(rhs < (*this)); }
+
+  bool operator!=(RouteWeight const & rhs) const { return !((*this) == rhs); }
+
+  bool operator>(RouteWeight const & rhs) const { return rhs < (*this); }
+
+  bool operator>=(RouteWeight const & rhs) const { return !((*this) < rhs); }
+
+  RouteWeight operator+(RouteWeight const & rhs) const
+  {
+    return RouteWeight(m_weight + rhs.m_weight);
+  }
+
+  RouteWeight operator-(RouteWeight const & rhs) const
+  {
+    return RouteWeight(m_weight - rhs.m_weight);
+  }
+
+  RouteWeight & operator+=(RouteWeight const & rhs)
+  {
+    m_weight += rhs.m_weight;
+    return *this;
+  }
+
+  RouteWeight operator-() const { return RouteWeight(-m_weight); }
+
+private:
+  double m_weight = 0.0;
+};
+
+std::ostream & operator<<(std::ostream & os, RouteWeight const & routeWeight);
+
+RouteWeight operator*(double lhs, RouteWeight const & rhs);
+
+template <>
+constexpr RouteWeight GetAStarWeightMax<RouteWeight>()
+{
+  return RouteWeight(std::numeric_limits<double>::max());
+}
+
+template <>
+constexpr RouteWeight GetAStarWeightZero<RouteWeight>()
+{
+  return RouteWeight(0.0);
+}
+
+template <>
+constexpr RouteWeight GetAStarWeightEpsilon<RouteWeight>()
+{
+  return RouteWeight(GetAStarWeightEpsilon<double>());
+}
+
+}  // namespace routing
diff --git a/routing/routing.pro b/routing/routing.pro
index 2c11c4358c..823bcdd534 100644
--- a/routing/routing.pro
+++ b/routing/routing.pro
@@ -51,6 +51,7 @@ SOURCES += \
     road_graph_router.cpp \
     road_index.cpp \
     route.cpp \
+    route_weight.cpp \
     router.cpp \
     router_delegate.cpp \
     routing_algorithm.cpp \
@@ -72,6 +73,7 @@ SOURCES += \
 HEADERS += \
     async_router.hpp \
     base/astar_algorithm.hpp \
+    base/astar_weight.hpp \
     base/followed_polyline.hpp \
     bicycle_directions.hpp \
     checkpoints.hpp \
@@ -115,6 +117,7 @@ HEADERS += \
     road_point.hpp \
     route.hpp \
     route_point.hpp \
+    route_weight.hpp \
     router.hpp \
     router_delegate.hpp \
     routing_algorithm.hpp \
diff --git a/routing/routing_algorithm.cpp b/routing/routing_algorithm.cpp
index 334e521bd7..8540a834ba 100644
--- a/routing/routing_algorithm.cpp
+++ b/routing/routing_algorithm.cpp
@@ -50,6 +50,7 @@ class RoadGraph
 public:
   using TVertexType = Junction;
   using TEdgeType = WeightedEdge;
+  using TWeightType = double;
 
   RoadGraph(IRoadGraph const & roadGraph)
     : m_roadGraph(roadGraph)
@@ -135,7 +136,7 @@ IRoutingAlgorithm::Result AStarRoutingAlgorithm::CalculateRoute(IRoadGraph const
                                                                 Junction const & startPos,
                                                                 Junction const & finalPos,
                                                                 RouterDelegate const & delegate,
-                                                                RoutingResult<Junction> & path)
+                                                                RoutingResult<IRoadGraph::Vertex, IRoadGraph::Weight> & path)
 {
   AStarProgress progress(0, 95);
   uint32_t visitCount = 0;
@@ -164,7 +165,7 @@ IRoutingAlgorithm::Result AStarRoutingAlgorithm::CalculateRoute(IRoadGraph const
 
 IRoutingAlgorithm::Result AStarBidirectionalRoutingAlgorithm::CalculateRoute(
     IRoadGraph const & graph, Junction const & startPos, Junction const & finalPos,
-    RouterDelegate const & delegate, RoutingResult<Junction> & path)
+    RouterDelegate const & delegate, RoutingResult<IRoadGraph::Vertex, IRoadGraph::Weight> & path)
 {
   AStarProgress progress(0, 95);
   uint32_t visitCount = 0;
diff --git a/routing/routing_algorithm.hpp b/routing/routing_algorithm.hpp
index 437494734e..1101ee2782 100644
--- a/routing/routing_algorithm.hpp
+++ b/routing/routing_algorithm.hpp
@@ -27,7 +27,7 @@ public:
 
   virtual Result CalculateRoute(IRoadGraph const & graph, Junction const & startPos,
                                 Junction const & finalPos, RouterDelegate const & delegate,
-                                RoutingResult<Junction> & path) = 0;
+                                RoutingResult<IRoadGraph::Vertex, IRoadGraph::Weight> & path) = 0;
 };
 
 string DebugPrint(IRoutingAlgorithm::Result const & result);
@@ -39,7 +39,7 @@ public:
   // IRoutingAlgorithm overrides:
   Result CalculateRoute(IRoadGraph const & graph, Junction const & startPos,
                         Junction const & finalPos, RouterDelegate const & delegate,
-                        RoutingResult<Junction> & path) override;
+                        RoutingResult<IRoadGraph::Vertex, IRoadGraph::Weight> & path) override;
 };
 
 // AStar-bidirectional routing algorithm implementation
@@ -49,7 +49,7 @@ public:
   // IRoutingAlgorithm overrides:
   Result CalculateRoute(IRoadGraph const & graph, Junction const & startPos,
                         Junction const & finalPos, RouterDelegate const & delegate,
-                        RoutingResult<Junction> & path) override;
+                        RoutingResult<IRoadGraph::Vertex, IRoadGraph::Weight> & path) override;
 };
 
 }  // namespace routing
diff --git a/routing/routing_tests/astar_algorithm_test.cpp b/routing/routing_tests/astar_algorithm_test.cpp
index 40c40b6015..7a0f82bbc2 100644
--- a/routing/routing_tests/astar_algorithm_test.cpp
+++ b/routing/routing_tests/astar_algorithm_test.cpp
@@ -26,6 +26,7 @@ class UndirectedGraph
 public:
   using TVertexType = unsigned;
   using TEdgeType = Edge;
+  using TWeightType = double;
 
   void AddEdge(unsigned u, unsigned v, unsigned w)
   {
@@ -63,7 +64,7 @@ void TestAStar(UndirectedGraph & graph, vector<unsigned> const & expectedRoute,
 {
   TAlgorithm algo;
 
-  RoutingResult<unsigned> actualRoute;
+  RoutingResult<unsigned /* VertexType */, double /* WeightType */> actualRoute;
   TEST_EQUAL(TAlgorithm::Result::OK, algo.FindPath(graph, 0u, 4u, actualRoute), ());
   TEST_EQUAL(expectedRoute, actualRoute.path, ());
   TEST_ALMOST_EQUAL_ULPS(expectedDistance, actualRoute.distance, ());
@@ -105,7 +106,7 @@ UNIT_TEST(AdjustRoute)
   vector<Edge> const prevRoute = {{0, 0}, {1, 1}, {2, 1}, {3, 1}, {4, 1}, {5, 1}};
 
   TAlgorithm algo;
-  RoutingResult<unsigned> result;
+  RoutingResult<unsigned /* VertexType */, double /* WeightType */> result;
   auto code = algo.AdjustRoute(graph, 6 /* start */, prevRoute, 1.0 /* limit */, result,
                                my::Cancellable(), nullptr /* onVisitedVertexCallback */);
 
@@ -126,7 +127,7 @@ UNIT_TEST(AdjustRouteNoPath)
   vector<Edge> const prevRoute = {{0, 0}, {1, 1}, {2, 1}, {3, 1}, {4, 1}, {5, 1}};
 
   TAlgorithm algo;
-  RoutingResult<unsigned> result;
+  RoutingResult<unsigned /* VertexType */, double /* WeightType */> result;
   auto code = algo.AdjustRoute(graph, 6 /* start */, prevRoute, 1.0 /* limit */, result,
                                my::Cancellable(), nullptr /* onVisitedVertexCallback */);
 
@@ -147,7 +148,7 @@ UNIT_TEST(AdjustRouteOutOfLimit)
   vector<Edge> const prevRoute = {{0, 0}, {1, 1}, {2, 1}, {3, 1}, {4, 1}, {5, 1}};
 
   TAlgorithm algo;
-  RoutingResult<unsigned> result;
+  RoutingResult<unsigned /* VertexType */, double /* WeightType */> result;
   auto code = algo.AdjustRoute(graph, 6 /* start */, prevRoute, 1.0 /* limit */, result,
                                my::Cancellable(), nullptr /* onVisitedVertexCallback */);
 
diff --git a/routing/routing_tests/astar_router_test.cpp b/routing/routing_tests/astar_router_test.cpp
index 2645807d58..516e479dc0 100644
--- a/routing/routing_tests/astar_router_test.cpp
+++ b/routing/routing_tests/astar_router_test.cpp
@@ -30,7 +30,7 @@ void TestAStarRouterMock(Junction const & startPos, Junction const & finalPos,
   InitRoadGraphMockSourceWithTest2(graph);
 
   RouterDelegate delegate;
-  RoutingResult<Junction> result;
+  RoutingResult<Junction, double /* WeightType */> result;
   TRoutingAlgorithm algorithm;
   TEST_EQUAL(TRoutingAlgorithm::Result::OK,
              algorithm.CalculateRoute(graph, startPos, finalPos, delegate, result), ());
@@ -98,7 +98,7 @@ UNIT_TEST(AStarRouter_SimpleGraph_RouteIsFound)
       MakeJunctionForTesting(m2::PointD(0, 60)), MakeJunctionForTesting(m2::PointD(40, 100))};
 
   RouterDelegate delegate;
-  RoutingResult<Junction> result;
+  RoutingResult<Junction, double /* WeightType */> result;
   TRoutingAlgorithm algorithm;
   TEST_EQUAL(TRoutingAlgorithm::Result::OK,
              algorithm.CalculateRoute(graph, startPos, finalPos, delegate, result), ());
@@ -167,7 +167,7 @@ UNIT_TEST(AStarRouter_SimpleGraph_RoutesInConnectedComponents)
     {
       RouterDelegate delegate;
       Junction const finalPos = roadInfo_2[j].m_junctions[0];
-      RoutingResult<Junction> result;
+      RoutingResult<Junction, double /* WeightType */> result;
       TEST_EQUAL(TRoutingAlgorithm::Result::NoPath,
                  algorithm.CalculateRoute(graph, startPos, finalPos, delegate, result), ());
       TEST_EQUAL(TRoutingAlgorithm::Result::NoPath,
@@ -183,7 +183,7 @@ UNIT_TEST(AStarRouter_SimpleGraph_RoutesInConnectedComponents)
     {
       RouterDelegate delegate;
       Junction const finalPos = roadInfo_1[j].m_junctions[0];
-      RoutingResult<Junction> result;
+      RoutingResult<Junction, double /* WeightType */> result;
       TEST_EQUAL(TRoutingAlgorithm::Result::OK,
                  algorithm.CalculateRoute(graph, startPos, finalPos, delegate, result), ());
       TEST_EQUAL(TRoutingAlgorithm::Result::OK,
@@ -199,7 +199,7 @@ UNIT_TEST(AStarRouter_SimpleGraph_RoutesInConnectedComponents)
     {
       RouterDelegate delegate;
       Junction const finalPos = roadInfo_2[j].m_junctions[0];
-      RoutingResult<Junction> result;
+      RoutingResult<Junction, double /* WeightType */> result;
       TEST_EQUAL(TRoutingAlgorithm::Result::OK,
                  algorithm.CalculateRoute(graph, startPos, finalPos, delegate, result), ());
       TEST_EQUAL(TRoutingAlgorithm::Result::OK,
@@ -227,7 +227,7 @@ UNIT_TEST(AStarRouter_SimpleGraph_PickTheFasterRoad1)
   // path3 = 1/5 + 8/4 + 1/5 = 2.4
 
   RouterDelegate delegate;
-  RoutingResult<Junction> result;
+  RoutingResult<Junction, double /* WeightType */> result;
   TRoutingAlgorithm algorithm;
   TEST_EQUAL(TRoutingAlgorithm::Result::OK,
              algorithm.CalculateRoute(graph, MakeJunctionForTesting(m2::PointD(2, 2)),
@@ -262,7 +262,7 @@ UNIT_TEST(AStarRouter_SimpleGraph_PickTheFasterRoad2)
   // path3 = 1/5 + 8/4.4 + 1/5 = 2.2
 
   RouterDelegate delegate;
-  RoutingResult<Junction> result;
+  RoutingResult<Junction, double /* WeightType */> result;
   TRoutingAlgorithm algorithm;
   TEST_EQUAL(TRoutingAlgorithm::Result::OK,
              algorithm.CalculateRoute(graph, MakeJunctionForTesting(m2::PointD(2, 2)),
@@ -293,7 +293,7 @@ UNIT_TEST(AStarRouter_SimpleGraph_PickTheFasterRoad3)
   // path3 = 1/5 + 8/4.9 + 1/5 = 2.03
 
   RouterDelegate delegate;
-  RoutingResult<Junction> result;
+  RoutingResult<Junction, double /* WeightType */> result;
   TRoutingAlgorithm algorithm;
   TEST_EQUAL(TRoutingAlgorithm::Result::OK,
              algorithm.CalculateRoute(graph, MakeJunctionForTesting(m2::PointD(2, 2)),
diff --git a/routing/routing_tests/cross_mwm_connector_test.cpp b/routing/routing_tests/cross_mwm_connector_test.cpp
index 4260c49e3c..8d3c886ab5 100644
--- a/routing/routing_tests/cross_mwm_connector_test.cpp
+++ b/routing/routing_tests/cross_mwm_connector_test.cpp
@@ -143,7 +143,7 @@ UNIT_TEST(TwoWayExit)
 
 UNIT_TEST(Serialization)
 {
-  float constexpr kEdgesWeight = 4444;
+  RouteWeight constexpr kEdgesWeight = RouteWeight(4444.0);
 
   vector<uint8_t> buffer;
   {
@@ -159,7 +159,7 @@ UNIT_TEST(Serialization)
       CrossMwmConnectorSerializer::AddTransition(transition, kCarMask, carConnector);
 
     carConnector.FillWeights(
-        [](Segment const & enter, Segment const & exit) { return kEdgesWeight; });
+        [&](Segment const & enter, Segment const & exit) { return kEdgesWeight; });
 
     serial::CodingParams const codingParams;
     MemWriter<vector<uint8_t>> writer(buffer);
@@ -244,9 +244,15 @@ UNIT_TEST(Serialization)
 UNIT_TEST(WeightsSerialization)
 {
   size_t constexpr kNumTransitions = 3;
-  vector<double> const weights = {
-      4.0,  20.0, CrossMwmConnector::kNoRoute, 12.0, CrossMwmConnector::kNoRoute, 40.0, 48.0,
-      24.0, 12.0};
+  vector<RouteWeight> const weights = {RouteWeight(4.0),
+                                       RouteWeight(20.0),
+                                       RouteWeight(CrossMwmConnector::kNoRoute),
+                                       RouteWeight(12.0),
+                                       RouteWeight(CrossMwmConnector::kNoRoute),
+                                       RouteWeight(40.0),
+                                       RouteWeight(48.0),
+                                       RouteWeight(24.0),
+                                       RouteWeight(12.0)};
   TEST_EQUAL(weights.size(), kNumTransitions * kNumTransitions, ());
 
   vector<uint8_t> buffer;
@@ -305,7 +311,7 @@ UNIT_TEST(WeightsSerialization)
     for (uint32_t exitId = 0; exitId < kNumTransitions; ++exitId)
     {
       auto const weight = weights[weightIdx];
-      if (weight != CrossMwmConnector::kNoRoute)
+      if (weight != RouteWeight(CrossMwmConnector::kNoRoute))
       {
         expectedEdges.emplace_back(Segment(mwmId, exitId, 1 /* segmentIdx */, false /* forward */),
                                    weight);
diff --git a/routing/routing_tests/index_graph_tools.cpp b/routing/routing_tests/index_graph_tools.cpp
index 8700d7c869..66efd2efad 100644
--- a/routing/routing_tests/index_graph_tools.cpp
+++ b/routing/routing_tests/index_graph_tools.cpp
@@ -275,13 +275,13 @@ AStarAlgorithm<IndexGraphStarter>::Result CalculateRoute(IndexGraphStarter & sta
                                                          double & timeSec)
 {
   AStarAlgorithm<IndexGraphStarter> algorithm;
-  RoutingResult<Segment> routingResult;
+  RoutingResult<Segment, RouteWeight> routingResult;
 
   auto const resultCode = algorithm.FindPathBidirectional(
       starter, starter.GetStart(), starter.GetFinish(), routingResult, {} /* cancellable */,
       {} /* onVisitedVertexCallback */);
 
-  timeSec = routingResult.distance;
+  timeSec = routingResult.distance.GetWeight();
   roadPoints = routingResult.path;
   return resultCode;
 }
diff --git a/routing/segment.hpp b/routing/segment.hpp
index cd476c7e7b..e8001894e1 100644
--- a/routing/segment.hpp
+++ b/routing/segment.hpp
@@ -2,10 +2,11 @@
 
 #include "routing/num_mwm_id.hpp"
 #include "routing/road_point.hpp"
+#include "routing/route_weight.hpp"
 
-#include "std/cstdint.hpp"
-#include "std/sstream.hpp"
-#include "std/string.hpp"
+#include <cstdint>
+#include <sstream>
+#include <string>
 
 namespace routing
 {
@@ -74,9 +75,12 @@ private:
 class SegmentEdge final
 {
 public:
-  SegmentEdge(Segment const & target, double weight) : m_target(target), m_weight(weight) {}
+  SegmentEdge(Segment const & target, RouteWeight const & weight)
+    : m_target(target), m_weight(weight)
+  {
+  }
   Segment const & GetTarget() const { return m_target; }
-  double GetWeight() const { return m_weight; }
+  RouteWeight const & GetWeight() const { return m_weight; }
 
   bool operator==(SegmentEdge const & edge) const
   {
@@ -93,20 +97,20 @@ public:
 private:
   // Target is vertex going to for outgoing edges, vertex going from for ingoing edges.
   Segment m_target;
-  double m_weight;
+  RouteWeight m_weight;
 };
 
-inline string DebugPrint(Segment const & segment)
+inline std::string DebugPrint(Segment const & segment)
 {
-  ostringstream out;
+  std::ostringstream out;
   out << "Segment(" << segment.GetMwmId() << ", " << segment.GetFeatureId() << ", "
       << segment.GetSegmentIdx() << ", " << segment.IsForward() << ")";
   return out.str();
 }
 
-inline string DebugPrint(SegmentEdge const & edge)
+inline std::string DebugPrint(SegmentEdge const & edge)
 {
-  ostringstream out;
+  std::ostringstream out;
   out << "Edge(" << DebugPrint(edge.GetTarget()) << ", " << edge.GetWeight() << ")";
   return out.str();
 }
diff --git a/routing/world_graph.cpp b/routing/world_graph.cpp
index c7090bcfec..a831e219a8 100644
--- a/routing/world_graph.cpp
+++ b/routing/world_graph.cpp
@@ -55,9 +55,10 @@ void WorldGraph::GetIngoingEdgesList(Segment const & segment, vector<SegmentEdge
   GetEdgeList(segment, false /* isOutgoing */, false /* isLeap */, edges);
 }
 
-double WorldGraph::HeuristicCostEstimate(Segment const & from, Segment const & to)
+RouteWeight WorldGraph::HeuristicCostEstimate(Segment const & from, Segment const & to)
 {
-  return m_estimator->CalcHeuristic(GetPoint(from, true /* front */), GetPoint(to, true /* front */));
+  return RouteWeight(
+      m_estimator->CalcHeuristic(GetPoint(from, true /* front */), GetPoint(to, true /* front */)));
 }
 
 void WorldGraph::GetTwins(Segment const & segment, bool isOutgoing, vector<SegmentEdge> & edges)
@@ -69,7 +70,7 @@ void WorldGraph::GetTwins(Segment const & segment, bool isOutgoing, vector<Segme
     m2::PointD const & from = GetPoint(segment, true /* front */);
     m2::PointD const & to = GetPoint(twin, true /* front */);
     double const weight = m_estimator->CalcHeuristic(from, to);
-    edges.emplace_back(twin, weight);
+    edges.emplace_back(twin, RouteWeight(weight));
   }
 }
 
diff --git a/routing/world_graph.hpp b/routing/world_graph.hpp
index 8d3ecb10ca..d1c88dc4f3 100644
--- a/routing/world_graph.hpp
+++ b/routing/world_graph.hpp
@@ -20,6 +20,7 @@ public:
   // AStarAlgorithm types aliases:
   using TVertexType = IndexGraph::TVertexType;
   using TEdgeType = IndexGraph::TEdgeType;
+  using TWeightType = IndexGraph::TWeightType;
 
   // CheckGraphConnectivity() types aliases:
   using Vertex = TVertexType;
@@ -56,7 +57,7 @@ public:
   // Interface for AStarAlgorithm:
   void GetOutgoingEdgesList(Segment const & segment, vector<SegmentEdge> & edges);
   void GetIngoingEdgesList(Segment const & segment, vector<SegmentEdge> & edges);
-  double HeuristicCostEstimate(Segment const & from, Segment const & to);
+  RouteWeight HeuristicCostEstimate(Segment const & from, Segment const & to);
 
   template <typename Fn>
   void ForEachTransition(NumMwmId numMwmId, bool isEnter, Fn && fn)
diff --git a/xcode/routing/routing.xcodeproj/project.pbxproj b/xcode/routing/routing.xcodeproj/project.pbxproj
index 64f9bcf08d..104e3468e0 100644
--- a/xcode/routing/routing.xcodeproj/project.pbxproj
+++ b/xcode/routing/routing.xcodeproj/project.pbxproj
@@ -56,6 +56,9 @@
 		3462FDAD1DC1E5BF00906FD7 /* libopening_hours.a in Frameworks */ = {isa = PBXBuildFile; fileRef = 3462FDAC1DC1E5BF00906FD7 /* libopening_hours.a */; };
 		349D1CE01E3F589900A878FD /* restrictions_serialization.cpp in Sources */ = {isa = PBXBuildFile; fileRef = 349D1CDE1E3F589900A878FD /* restrictions_serialization.cpp */; };
 		349D1CE11E3F589900A878FD /* restrictions_serialization.hpp in Headers */ = {isa = PBXBuildFile; fileRef = 349D1CDF1E3F589900A878FD /* restrictions_serialization.hpp */; };
+		40A111CD1F2F6776005E6AD5 /* route_weight.cpp in Sources */ = {isa = PBXBuildFile; fileRef = 40A111CB1F2F6776005E6AD5 /* route_weight.cpp */; };
+		40A111CE1F2F6776005E6AD5 /* route_weight.hpp in Headers */ = {isa = PBXBuildFile; fileRef = 40A111CC1F2F6776005E6AD5 /* route_weight.hpp */; };
+		40A111D01F2F9704005E6AD5 /* astar_weight.hpp in Headers */ = {isa = PBXBuildFile; fileRef = 40A111CF1F2F9704005E6AD5 /* astar_weight.hpp */; };
 		56099E291CC7C97D00A7772A /* loaded_path_segment.hpp in Headers */ = {isa = PBXBuildFile; fileRef = 56099E251CC7C97D00A7772A /* loaded_path_segment.hpp */; };
 		56099E2A1CC7C97D00A7772A /* routing_result_graph.hpp in Headers */ = {isa = PBXBuildFile; fileRef = 56099E261CC7C97D00A7772A /* routing_result_graph.hpp */; };
 		56099E2B1CC7C97D00A7772A /* turn_candidate.hpp in Headers */ = {isa = PBXBuildFile; fileRef = 56099E271CC7C97D00A7772A /* turn_candidate.hpp */; };
@@ -322,6 +325,9 @@
 		349D1CDF1E3F589900A878FD /* restrictions_serialization.hpp */ = {isa = PBXFileReference; fileEncoding = 4; lastKnownFileType = sourcecode.cpp.h; path = restrictions_serialization.hpp; sourceTree = "<group>"; };
 		34F558351DBF2A2600A4FC11 /* common-debug.xcconfig */ = {isa = PBXFileReference; lastKnownFileType = text.xcconfig; name = "common-debug.xcconfig"; path = "../common-debug.xcconfig"; sourceTree = "<group>"; };
 		34F558361DBF2A2600A4FC11 /* common-release.xcconfig */ = {isa = PBXFileReference; lastKnownFileType = text.xcconfig; name = "common-release.xcconfig"; path = "../common-release.xcconfig"; sourceTree = "<group>"; };
+		40A111CB1F2F6776005E6AD5 /* route_weight.cpp */ = {isa = PBXFileReference; fileEncoding = 4; lastKnownFileType = sourcecode.cpp.cpp; path = route_weight.cpp; sourceTree = "<group>"; };
+		40A111CC1F2F6776005E6AD5 /* route_weight.hpp */ = {isa = PBXFileReference; fileEncoding = 4; lastKnownFileType = sourcecode.cpp.h; path = route_weight.hpp; sourceTree = "<group>"; };
+		40A111CF1F2F9704005E6AD5 /* astar_weight.hpp */ = {isa = PBXFileReference; fileEncoding = 4; lastKnownFileType = sourcecode.cpp.h; path = astar_weight.hpp; sourceTree = "<group>"; };
 		56099E251CC7C97D00A7772A /* loaded_path_segment.hpp */ = {isa = PBXFileReference; fileEncoding = 4; lastKnownFileType = sourcecode.cpp.h; path = loaded_path_segment.hpp; sourceTree = "<group>"; };
 		56099E261CC7C97D00A7772A /* routing_result_graph.hpp */ = {isa = PBXFileReference; fileEncoding = 4; lastKnownFileType = sourcecode.cpp.h; path = routing_result_graph.hpp; sourceTree = "<group>"; };
 		56099E271CC7C97D00A7772A /* turn_candidate.hpp */ = {isa = PBXFileReference; fileEncoding = 4; lastKnownFileType = sourcecode.cpp.h; path = turn_candidate.hpp; sourceTree = "<group>"; };
@@ -592,6 +598,7 @@
 		671F58BA1B874EA20032311E /* base */ = {
 			isa = PBXGroup;
 			children = (
+				40A111CF1F2F9704005E6AD5 /* astar_weight.hpp */,
 				671F58BB1B874EC80032311E /* followed_polyline.cpp */,
 				671F58BC1B874EC80032311E /* followed_polyline.hpp */,
 				A1616E2D1B6B60B3003F078E /* astar_progress.hpp */,
@@ -732,6 +739,8 @@
 		675343FA1A3F640D00A0A8C3 /* routing */ = {
 			isa = PBXGroup;
 			children = (
+				40A111CB1F2F6776005E6AD5 /* route_weight.cpp */,
+				40A111CC1F2F6776005E6AD5 /* route_weight.hpp */,
 				5694CEC51EBA25F7004576D3 /* road_access_serialization.cpp */,
 				5694CEC61EBA25F7004576D3 /* road_access_serialization.hpp */,
 				5694CEC71EBA25F7004576D3 /* road_access.cpp */,
@@ -927,12 +936,14 @@
 				670EE5721B664796001E8064 /* directions_engine.hpp in Headers */,
 				56C439291E93BF8C00998E29 /* cross_mwm_graph.hpp in Headers */,
 				0C81E1541F02589800DC66DF /* traffic_stash.hpp in Headers */,
+				40A111D01F2F9704005E6AD5 /* astar_weight.hpp in Headers */,
 				0C8705051E0182F200BCAF71 /* route_point.hpp in Headers */,
 				A1876BC71BB19C4300C9C743 /* speed_camera.hpp in Headers */,
 				56EA2FD51D8FD8590083F01A /* routing_helpers.hpp in Headers */,
 				0C15B8021F02A61B0058E253 /* checkpoints.hpp in Headers */,
 				0C5F5D211E798B0400307B98 /* cross_mwm_connector_serialization.hpp in Headers */,
 				0C0DF9221DE898B70055A22F /* index_graph_starter.hpp in Headers */,
+				40A111CE1F2F6776005E6AD5 /* route_weight.hpp in Headers */,
 				0C090C881E4E276700D52AFD /* world_graph.hpp in Headers */,
 				0C08AA351DF83223004195DD /* index_graph_serialization.hpp in Headers */,
 				5694CECD1EBA25F7004576D3 /* road_access.hpp in Headers */,
@@ -1185,6 +1196,7 @@
 				0C81E1531F02589800DC66DF /* traffic_stash.cpp in Sources */,
 				0CF5E8AA1E8EA7A1001ED497 /* coding_test.cpp in Sources */,
 				675344191A3F644F00A0A8C3 /* osrm2feature_map.cpp in Sources */,
+				40A111CD1F2F6776005E6AD5 /* route_weight.cpp in Sources */,
 				670D049E1B0B4A970013A7AC /* nearest_edge_finder.cpp in Sources */,
 				0C5F5D251E798B3800307B98 /* cross_mwm_connector_test.cpp in Sources */,
 				674F9BD61B0A580E00704FFA /* turns_generator.cpp in Sources */,