Add number of nontransit crossings to RouteWeight, add penality

26 files changed, 282 insertions, 90 deletions

diff --git a/generator/routing_index_generator.cpp b/generator/routing_index_generator.cpp
index c446e8de10..aeabf2d6e7 100644
--- a/generator/routing_index_generator.cpp
+++ b/generator/routing_index_generator.cpp
@@ -175,10 +175,10 @@ private:
 
 // Calculate distance from the starting border point to the transition along the border.
 // It could be measured clockwise or counterclockwise, direction doesn't matter.
-RouteWeight CalcDistanceAlongTheBorders(vector<m2::RegionD> const & borders,
-                                        CrossMwmConnectorSerializer::Transition const & transition)
+double CalcDistanceAlongTheBorders(vector<m2::RegionD> const & borders,
+                                   CrossMwmConnectorSerializer::Transition const & transition)
 {
-  RouteWeight distance = GetAStarWeightZero<RouteWeight>();
+  auto distance = GetAStarWeightZero<double>();
 
   for (m2::RegionD const & region : borders)
   {
@@ -192,11 +192,11 @@ RouteWeight CalcDistanceAlongTheBorders(vector<m2::RegionD> const & borders,
       if (m2::RegionD::IsIntersect(transition.GetBackPoint(), transition.GetFrontPoint(), *prev,
                                    curr, intersection))
       {
-        distance += RouteWeight(prev->Length(intersection));
+        distance += prev->Length(intersection);
         return distance;
       }
 
-      distance += RouteWeight(prev->Length(curr));
+      distance += prev->Length(curr);
       prev = &curr;
     }
   }
@@ -324,13 +324,13 @@ 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 RouteWeight(CrossMwmConnector::kNoRoute);
+      return CrossMwmConnector::kNoRoute;
 
     auto it1 = it0->second.find(exit);
     if (it1 == it0->second.end())
-      return RouteWeight(CrossMwmConnector::kNoRoute);
+      return CrossMwmConnector::kNoRoute;
 
-    return it1->second;
+    return it1->second.ToCrossMwmWeight();
   });
 
   LOG(LINFO, ("Leaps finished, elapsed:", timer.ElapsedSeconds(), "seconds, routes found:",
diff --git a/routing/CMakeLists.txt b/routing/CMakeLists.txt
index 5e54c2e88e..cc9117d0f0 100644
--- a/routing/CMakeLists.txt
+++ b/routing/CMakeLists.txt
@@ -15,6 +15,7 @@ set(
   base/astar_weight.hpp
   base/followed_polyline.cpp
   base/followed_polyline.hpp
+  base/routing_result.hpp
   bicycle_directions.cpp
   bicycle_directions.hpp
   checkpoint_predictor.cpp
diff --git a/routing/base/astar_algorithm.hpp b/routing/base/astar_algorithm.hpp
index 072ae2e5a3..6fd675db9d 100644
--- a/routing/base/astar_algorithm.hpp
+++ b/routing/base/astar_algorithm.hpp
@@ -1,6 +1,7 @@
 #pragma once
 
 #include "routing/base/astar_weight.hpp"
+#include "routing/base/routing_result.hpp"
 
 #include "base/assert.hpp"
 #include "base/cancellable.hpp"
@@ -13,22 +14,6 @@
 
 namespace routing
 {
-
-template <typename TVertexType, typename TWeightType>
-struct RoutingResult
-{
-  std::vector<TVertexType> path;
-  TWeightType distance;
-
-  RoutingResult() : distance(GetAStarWeightZero<TWeightType>()) {}
-
-  void Clear()
-  {
-    path.clear();
-    distance = GetAStarWeightZero<TWeightType>();
-  }
-};
-
 template <typename TGraph>
 class AStarAlgorithm
 {
diff --git a/routing/base/routing_result.hpp b/routing/base/routing_result.hpp
new file mode 100644
index 0000000000..ec2837ffb2
--- /dev/null
+++ b/routing/base/routing_result.hpp
@@ -0,0 +1,21 @@
+#pragma once
+
+#include "routing/base/astar_weight.hpp"
+
+#include <vector>
+
+namespace routing
+{
+template <typename TVertexType, typename TWeightType>
+struct RoutingResult
+{
+  std::vector<TVertexType> path;
+  TWeightType distance;
+  RoutingResult() : distance(GetAStarWeightZero<TWeightType>()) {}
+  void Clear()
+  {
+    path.clear();
+    distance = GetAStarWeightZero<TWeightType>();
+  }
+};
+}  // namespace routing
diff --git a/routing/cross_mwm_connector.cpp b/routing/cross_mwm_connector.cpp
index 64297d37a0..1b17386f65 100644
--- a/routing/cross_mwm_connector.cpp
+++ b/routing/cross_mwm_connector.cpp
@@ -149,8 +149,8 @@ std::string DebugPrint(CrossMwmConnector::WeightsLoadState state)
 void CrossMwmConnector::AddEdge(Segment const & segment, Weight weight,
                                 std::vector<SegmentEdge> & edges) const
 {
-  if (weight != static_cast<Weight>(kNoRoute))
-    edges.emplace_back(segment, RouteWeight(static_cast<double>(weight)));
+  if (weight != kNoRoute)
+    edges.emplace_back(segment, RouteWeight::FromCrossMwmWeight(weight));
 }
 
 CrossMwmConnector::Transition const & CrossMwmConnector::GetTransition(
diff --git a/routing/cross_mwm_connector.hpp b/routing/cross_mwm_connector.hpp
index 1b5d49ac72..904ca0637c 100644
--- a/routing/cross_mwm_connector.hpp
+++ b/routing/cross_mwm_connector.hpp
@@ -62,9 +62,9 @@ public:
     {
       for (Segment const & exit : m_exits)
       {
-        RouteWeight const weight = calcWeight(enter, exit);
+        auto 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.GetWeight())));
+        m_weights.push_back(static_cast<Weight>(std::ceil(weight)));
       }
     }
   }
diff --git a/routing/cross_mwm_osrm_graph.cpp b/routing/cross_mwm_osrm_graph.cpp
index 58c7aae429..d7aa3a1fb8 100644
--- a/routing/cross_mwm_osrm_graph.cpp
+++ b/routing/cross_mwm_osrm_graph.cpp
@@ -103,8 +103,9 @@ 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, RouteWeight(osrmEdge.GetWeight() * kOSRMWeightToSecondsMultiplier *
-                                          kAstarHeuristicFactor));
+  edges.emplace_back(
+      segment, RouteWeight::FromCrossMwmWeight(
+                   osrmEdge.GetWeight() * kOSRMWeightToSecondsMultiplier * kAstarHeuristicFactor));
 }
 }  // namespace
 
diff --git a/routing/cross_mwm_router.cpp b/routing/cross_mwm_router.cpp
index df4e6a15c6..5a04b2e314 100644
--- a/routing/cross_mwm_router.cpp
+++ b/routing/cross_mwm_router.cpp
@@ -1,8 +1,9 @@
 #include "routing/cross_mwm_router.hpp"
 
+#include "routing/base/astar_algorithm.hpp"
+#include "routing/base/routing_result.hpp"
 #include "routing/cross_mwm_road_graph.hpp"
 
-#include "base/astar_algorithm.hpp"
 #include "base/timer.hpp"
 
 namespace routing
diff --git a/routing/geometry.hpp b/routing/geometry.hpp
index aa432b27dd..d30cffa347 100644
--- a/routing/geometry.hpp
+++ b/routing/geometry.hpp
@@ -57,6 +57,8 @@ public:
     return pointId == 0 || pointId + 1 == GetPointsCount();
   }
 
+  void SetTransitAllowedForTests(bool transitAllowed) { m_isTransitAllowed = transitAllowed; }
+
 private:
   buffer_vector<Junction, 32> m_junctions;
   double m_speed = 0.0;
diff --git a/routing/index_graph.cpp b/routing/index_graph.cpp
index 27f91c479e..013576e364 100644
--- a/routing/index_graph.cpp
+++ b/routing/index_graph.cpp
@@ -112,13 +112,14 @@ void IndexGraph::GetIngoingEdgesList(Segment const & segment, vector<SegmentEdge
 RouteWeight IndexGraph::HeuristicCostEstimate(Segment const & from, Segment const & to)
 {
   return RouteWeight(
-      m_estimator->CalcHeuristic(GetPoint(from, true /* front */), GetPoint(to, true /* front */)));
+      m_estimator->CalcHeuristic(GetPoint(from, true /* front */), GetPoint(to, true /* front */)),
+      0);
 }
 
 RouteWeight IndexGraph::CalcSegmentWeight(Segment const & segment)
 {
   return RouteWeight(
-      m_estimator->CalcSegmentWeight(segment, m_geometry.GetRoad(segment.GetFeatureId())));
+      m_estimator->CalcSegmentWeight(segment, m_geometry.GetRoad(segment.GetFeatureId())), 0);
 }
 
 void IndexGraph::GetNeighboringEdges(Segment const & from, RoadPoint const & rp, bool isOutgoing,
@@ -168,11 +169,16 @@ void IndexGraph::GetNeighboringEdge(Segment const & from, Segment const & to, bo
   edges.emplace_back(to, weight);
 }
 
-RouteWeight IndexGraph::GetPenalties(Segment const & u, Segment const & v) const
+RouteWeight IndexGraph::GetPenalties(Segment const & u, Segment const & v)
 {
+  bool fromTransitAllowed = m_geometry.GetRoad(u.GetFeatureId()).IsTransitAllowed();
+  bool toTransitAllowed = m_geometry.GetRoad(v.GetFeatureId()).IsTransitAllowed();
+
+  uint32_t transitPenalty = fromTransitAllowed == toTransitAllowed ? 0 : 1;
+
   if (IsUTurn(u, v))
-    return RouteWeight(m_estimator->GetUTurnPenalty());
+    return RouteWeight(m_estimator->GetUTurnPenalty(), transitPenalty);
 
-  return RouteWeight(0.0);
+  return RouteWeight(0.0, transitPenalty);
 }
 }  // namespace routing
diff --git a/routing/index_graph.hpp b/routing/index_graph.hpp
index 459b7b69bd..7d65f5ee70 100644
--- a/routing/index_graph.hpp
+++ b/routing/index_graph.hpp
@@ -83,7 +83,7 @@ private:
                            vector<SegmentEdge> & edges);
   void GetNeighboringEdge(Segment const & from, Segment const & to, bool isOutgoing,
                           vector<SegmentEdge> & edges);
-  RouteWeight GetPenalties(Segment const & u, Segment const & v) const;
+  RouteWeight GetPenalties(Segment const & u, Segment const & v);
   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 e2273321f0..046143dd09 100644
--- a/routing/index_graph_starter.cpp
+++ b/routing/index_graph_starter.cpp
@@ -214,6 +214,38 @@ set<NumMwmId> IndexGraphStarter::GetMwms() const
   return mwms;
 }
 
+bool IndexGraphStarter::CheckRoutingResultMeetsRestrictions(
+    RoutingResult<Segment, RouteWeight> const & result) const
+{
+  uint32_t nontransitCrossAllowed = 0;
+  auto isRealOrPart = [this](Segment const & segment) {
+    if (!IsFakeSegment(segment))
+      return true;
+    return m_fake.m_fakeToReal.find(segment) != m_fake.m_fakeToReal.end();
+  };
+  auto isTransitAllowed = [this](Segment const & segment) {
+    auto real = segment;
+    bool const convertionResult = ConvertToReal(real);
+    CHECK(convertionResult, ());
+    return m_graph.GetRoadGeometry(real.GetMwmId(), real.GetFeatureId()).IsTransitAllowed();
+  };
+
+  auto const firstRealOrPart = find_if(result.path.begin(), result.path.end(), isRealOrPart);
+  if (firstRealOrPart != result.path.end() && !isTransitAllowed(*firstRealOrPart))
+    ++nontransitCrossAllowed;
+
+  auto const lastRealOrPart = find_if(result.path.rbegin(), result.path.rend(), isRealOrPart);
+  // If firstRealOrPart and lastRealOrPart point to the same segment increment
+  // nontransitCrossAllowed once
+  if (lastRealOrPart != result.path.rend() && (lastRealOrPart.base() - 1) != firstRealOrPart &&
+      !isTransitAllowed(*lastRealOrPart))
+  {
+    ++nontransitCrossAllowed;
+  }
+
+  return nontransitCrossAllowed >= result.distance.GetNontransitCross();
+}
+
 void IndexGraphStarter::GetEdgesList(Segment const & segment, bool isOutgoing,
                                      vector<SegmentEdge> & edges) const
 {
@@ -238,7 +270,7 @@ void IndexGraphStarter::GetEdgesList(Segment const & segment, bool isOutgoing,
     if (it != adjacentEdges.end())
     {
       for (auto const & s : it->second)
-        edges.emplace_back(s, RouteWeight(CalcSegmentWeight(isOutgoing ? s : segment)));
+        edges.emplace_back(s, CalcSegmentWeight(isOutgoing ? s : segment));
     }
   }
   else
@@ -249,24 +281,27 @@ void IndexGraphStarter::GetEdgesList(Segment const & segment, bool isOutgoing,
   AddFakeEdges(segment, edges);
 }
 
-double IndexGraphStarter::CalcSegmentWeight(Segment const & segment) const
+RouteWeight IndexGraphStarter::CalcSegmentWeight(Segment const & segment) const
 {
   if (!IsFakeSegment(segment))
   {
-    return m_graph.GetEstimator().CalcSegmentWeight(
-        segment, m_graph.GetRoadGeometry(segment.GetMwmId(), segment.GetFeatureId()));
+    return RouteWeight(
+        m_graph.GetEstimator().CalcSegmentWeight(
+            segment, m_graph.GetRoadGeometry(segment.GetMwmId(), segment.GetFeatureId())),
+        0);
   }
 
   auto const fakeVertexIt = m_fake.m_segmentToVertex.find(segment);
 
   CHECK(fakeVertexIt != m_fake.m_segmentToVertex.end(),
         ("Requested junction for invalid fake segment."));
-  return m_graph.GetEstimator().CalcLeapWeight(fakeVertexIt->second.GetPointFrom(),
-                                               fakeVertexIt->second.GetPointTo());
+  return RouteWeight(m_graph.GetEstimator().CalcLeapWeight(fakeVertexIt->second.GetPointFrom(),
+                                                           fakeVertexIt->second.GetPointTo()),
+                     0);
 }
 
-double IndexGraphStarter::CalcRouteSegmentWeight(vector<Segment> const & route,
-                                                 size_t segmentIndex) const
+RouteWeight IndexGraphStarter::CalcRouteSegmentWeight(vector<Segment> const & route,
+                                                      size_t segmentIndex) const
 {
   CHECK_LESS(
       segmentIndex, route.size(),
@@ -383,7 +418,7 @@ void IndexGraphStarter::AddStart(FakeEnding const & startEnding, FakeEnding cons
         // Check fake segment is connected to source segment.
         if (GetJunction(s, false /* front */) == GetJunction(segment, true) ||
             GetJunction(s, true) == GetJunction(segment, false))
-          fakeEdges.emplace_back(s, RouteWeight(edge.GetWeight()));
+          fakeEdges.emplace_back(s, edge.GetWeight());
       }
     }
     edges.insert(edges.end(), fakeEdges.begin(), fakeEdges.end());
@@ -414,8 +449,10 @@ void IndexGraphStarter::ConnectLeapToTransitions(Segment const & segment, bool i
   // point. So |isEnter| below should be set to true.
   m_graph.ForEachTransition(
       segment.GetMwmId(), !isOutgoing /* isEnter */, [&](Segment const & transition) {
-        edges.emplace_back(transition, RouteWeight(m_graph.GetEstimator().CalcLeapWeight(
-                                           segmentPoint, GetPoint(transition, isOutgoing))));
+        edges.emplace_back(transition,
+                           RouteWeight(m_graph.GetEstimator().CalcLeapWeight(
+                                           segmentPoint, GetPoint(transition, isOutgoing)),
+                                       0));
       });
 }
 
diff --git a/routing/index_graph_starter.hpp b/routing/index_graph_starter.hpp
index 72414bd358..2e9967809b 100644
--- a/routing/index_graph_starter.hpp
+++ b/routing/index_graph_starter.hpp
@@ -1,5 +1,6 @@
 #pragma once
 
+#include "routing/base/routing_result.hpp"
 #include "routing/index_graph.hpp"
 #include "routing/joint.hpp"
 #include "routing/num_mwm_id.hpp"
@@ -83,6 +84,11 @@ public:
 
   std::set<NumMwmId> GetMwms() const;
 
+  // Checks |result| meets nontransit crossing restrictions according to placement of
+  // |result.path| start and finish in transit/nontransit area and number of nontransit crosses
+  bool CheckRoutingResultMeetsRestrictions(
+      RoutingResult<Segment, RouteWeight> const & result) const;
+
   void GetEdgesList(Segment const & segment, bool isOutgoing,
                     std::vector<SegmentEdge> & edges) const;
 
@@ -99,11 +105,12 @@ public:
   RouteWeight HeuristicCostEstimate(TVertexType const & from, TVertexType const & to) const
   {
     return RouteWeight(m_graph.GetEstimator().CalcHeuristic(GetPoint(from, true /* front */),
-                                                            GetPoint(to, true /* front */)));
+                                                            GetPoint(to, true /* front */)),
+                       0);
   }
 
-  double CalcSegmentWeight(Segment const & segment) const;
-  double CalcRouteSegmentWeight(std::vector<Segment> const & route, size_t segmentIndex) const;
+  RouteWeight CalcSegmentWeight(Segment const & segment) const;
+  RouteWeight CalcRouteSegmentWeight(std::vector<Segment> const & route, size_t segmentIndex) const;
 
   bool IsLeap(NumMwmId mwmId) const;
 
diff --git a/routing/index_router.cpp b/routing/index_router.cpp
index 4c44b5b4c4..8ff50d8e64 100644
--- a/routing/index_router.cpp
+++ b/routing/index_router.cpp
@@ -2,6 +2,7 @@
 
 #include "routing/base/astar_algorithm.hpp"
 #include "routing/base/astar_progress.hpp"
+#include "routing/base/routing_result.hpp"
 #include "routing/bicycle_directions.hpp"
 #include "routing/index_graph.hpp"
 #include "routing/index_graph_loader.hpp"
@@ -532,6 +533,9 @@ IRouter::ResultCode IndexRouter::CalculateSubroute(Checkpoints const & checkpoin
   if (result != IRouter::NoError)
     return result;
 
+  if (!starter.CheckRoutingResultMeetsRestrictions(routingResult))
+    return IRouter::RouteNotFound;
+
   IRouter::ResultCode const leapsResult =
       ProcessLeaps(routingResult.path, delegate, starter.GetGraph().GetMode(), starter, subroute);
   if (leapsResult != IRouter::NoError)
@@ -580,8 +584,7 @@ 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(),
-                           RouteWeight(starter.CalcSegmentWeight(step.GetSegment())));
+    prevEdges.emplace_back(step.GetSegment(), starter.CalcSegmentWeight(step.GetSegment()));
   }
 
   uint32_t visitCount = 0;
@@ -603,7 +606,7 @@ IRouter::ResultCode IndexRouter::AdjustRoute(Checkpoints const & checkpoints,
   RoutingResult<Segment, RouteWeight> result;
   auto resultCode = ConvertResult<IndexGraphStarter>(
       algorithm.AdjustRoute(starter, starter.GetStartSegment(), prevEdges,
-                            RouteWeight(kAdjustLimitSec), result, delegate, onVisitJunction));
+                            RouteWeight(kAdjustLimitSec, 0), result, delegate, onVisitJunction));
   if (resultCode != IRouter::NoError)
     return resultCode;
 
@@ -785,7 +788,7 @@ IRouter::ResultCode IndexRouter::RedressRoute(vector<Segment> const & segments,
 
   for (size_t i = 0; i + 1 < numPoints; ++i)
   {
-    time += starter.CalcRouteSegmentWeight(segments, i);
+    time += starter.CalcRouteSegmentWeight(segments, i).GetWeight();
     times.emplace_back(static_cast<uint32_t>(i + 1), time);
   }
   
diff --git a/routing/route_weight.cpp b/routing/route_weight.cpp
index f962b6d345..a8645f457d 100644
--- a/routing/route_weight.cpp
+++ b/routing/route_weight.cpp
@@ -1,17 +1,26 @@
 #include "routing/route_weight.hpp"
 
+#include "routing/cross_mwm_connector.hpp"
+
 using namespace std;
 
 namespace routing
 {
+double RouteWeight::ToCrossMwmWeight() const
+{
+  if (m_nontransitCross > 0)
+    return CrossMwmConnector::kNoRoute;
+  return GetWeight();
+}
+
 ostream & operator<<(ostream & os, RouteWeight const & routeWeight)
 {
-  os << routeWeight.GetWeight();
+  os << "(" << routeWeight.GetNontransitCross() << ", " << routeWeight.GetWeight() << ")";
   return os;
 }
 
 RouteWeight operator*(double lhs, RouteWeight const & rhs)
 {
-  return RouteWeight(lhs * rhs.GetWeight());
+  return RouteWeight(lhs * rhs.GetWeight(), rhs.GetNontransitCross());
 }
 }  // namespace routing
diff --git a/routing/route_weight.hpp b/routing/route_weight.hpp
index adebf609bc..0119ae3957 100644
--- a/routing/route_weight.hpp
+++ b/routing/route_weight.hpp
@@ -2,6 +2,7 @@
 
 #include "routing/base/astar_weight.hpp"
 
+#include <cstdint>
 #include <iostream>
 #include <limits>
 
@@ -12,11 +13,22 @@ class RouteWeight final
 public:
   RouteWeight() = default;
 
-  constexpr explicit RouteWeight(double weight) : m_weight(weight) {}
+  constexpr RouteWeight(double weight, int32_t nontransitCross)
+    : m_weight(weight), m_nontransitCross(nontransitCross)
+  {
+  }
 
   double GetWeight() const { return m_weight; }
+  int32_t GetNontransitCross() const { return m_nontransitCross; }
+  static RouteWeight FromCrossMwmWeight(double weight) { return RouteWeight(weight, 0); }
+  double ToCrossMwmWeight() const;
 
-  bool operator<(RouteWeight const & rhs) const { return m_weight < rhs.m_weight; }
+  bool operator<(RouteWeight const & rhs) const
+  {
+    if (m_nontransitCross != rhs.m_nontransitCross)
+      return m_nontransitCross < rhs.m_nontransitCross;
+    return m_weight < rhs.m_weight;
+  }
 
   bool operator==(RouteWeight const & rhs) const { return !((*this) < rhs) && !(rhs < (*this)); }
 
@@ -28,24 +40,26 @@ public:
 
   RouteWeight operator+(RouteWeight const & rhs) const
   {
-    return RouteWeight(m_weight + rhs.m_weight);
+    return RouteWeight(m_weight + rhs.m_weight, m_nontransitCross + rhs.m_nontransitCross);
   }
 
   RouteWeight operator-(RouteWeight const & rhs) const
   {
-    return RouteWeight(m_weight - rhs.m_weight);
+    return RouteWeight(m_weight - rhs.m_weight, m_nontransitCross - rhs.m_nontransitCross);
   }
 
   RouteWeight & operator+=(RouteWeight const & rhs)
   {
     m_weight += rhs.m_weight;
+    m_nontransitCross += rhs.m_nontransitCross;
     return *this;
   }
 
-  RouteWeight operator-() const { return RouteWeight(-m_weight); }
+  RouteWeight operator-() const { return RouteWeight(-m_weight, -m_nontransitCross); }
 
 private:
   double m_weight = 0.0;
+  int32_t m_nontransitCross = 0;
 };
 
 std::ostream & operator<<(std::ostream & os, RouteWeight const & routeWeight);
@@ -55,19 +69,19 @@ RouteWeight operator*(double lhs, RouteWeight const & rhs);
 template <>
 constexpr RouteWeight GetAStarWeightMax<RouteWeight>()
 {
-  return RouteWeight(std::numeric_limits<double>::max());
+  return RouteWeight(std::numeric_limits<double>::max(), std::numeric_limits<int32_t>::max());
 }
 
 template <>
 constexpr RouteWeight GetAStarWeightZero<RouteWeight>()
 {
-  return RouteWeight(0.0);
+  return RouteWeight(0.0, 0);
 }
 
 template <>
 constexpr RouteWeight GetAStarWeightEpsilon<RouteWeight>()
 {
-  return RouteWeight(GetAStarWeightEpsilon<double>());
+  return RouteWeight(GetAStarWeightEpsilon<double>(), 0);
 }
 
 }  // namespace routing
diff --git a/routing/routing.pro b/routing/routing.pro
index 89cbb030bf..1ec33a943e 100644
--- a/routing/routing.pro
+++ b/routing/routing.pro
@@ -76,6 +76,7 @@ HEADERS += \
     base/astar_algorithm.hpp \
     base/astar_weight.hpp \
     base/followed_polyline.hpp \
+    base/routing_result.hpp \
     bicycle_directions.hpp \
     checkpoint_predictor.hpp \
     checkpoints.hpp \
diff --git a/routing/routing_algorithm.cpp b/routing/routing_algorithm.cpp
index 8540a834ba..3323122289 100644
--- a/routing/routing_algorithm.cpp
+++ b/routing/routing_algorithm.cpp
@@ -1,7 +1,8 @@
-#include "routing/road_graph.hpp"
 #include "routing/routing_algorithm.hpp"
+
 #include "routing/base/astar_algorithm.hpp"
 #include "routing/base/astar_progress.hpp"
+#include "routing/road_graph.hpp"
 
 #include "base/assert.hpp"
 
diff --git a/routing/routing_algorithm.hpp b/routing/routing_algorithm.hpp
index 1101ee2782..e1eb72467b 100644
--- a/routing/routing_algorithm.hpp
+++ b/routing/routing_algorithm.hpp
@@ -1,10 +1,10 @@
 #pragma once
 
-#include "base/cancellable.hpp"
-
+#include "routing/base/routing_result.hpp"
 #include "routing/road_graph.hpp"
 #include "routing/router.hpp"
-#include "routing/base/astar_algorithm.hpp"
+
+#include "base/cancellable.hpp"
 
 #include "std/functional.hpp"
 #include "std/string.hpp"
diff --git a/routing/routing_tests/astar_algorithm_test.cpp b/routing/routing_tests/astar_algorithm_test.cpp
index 7a0f82bbc2..cdcc237247 100644
--- a/routing/routing_tests/astar_algorithm_test.cpp
+++ b/routing/routing_tests/astar_algorithm_test.cpp
@@ -1,6 +1,8 @@
 #include "testing/testing.hpp"
 
 #include "routing/base/astar_algorithm.hpp"
+#include "routing/base/routing_result.hpp"
+
 #include "std/map.hpp"
 #include "std/utility.hpp"
 #include "std/vector.hpp"
diff --git a/routing/routing_tests/cross_mwm_connector_test.cpp b/routing/routing_tests/cross_mwm_connector_test.cpp
index 8d3c886ab5..a7802b066a 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)
 {
-  RouteWeight constexpr kEdgesWeight = RouteWeight(4444.0);
+  double constexpr kEdgesWeight = 4444.0;
 
   vector<uint8_t> buffer;
   {
@@ -231,28 +231,25 @@ UNIT_TEST(Serialization)
        ());
 
   TestEdges(connector, Segment(mwmId, 10, 1, true /* forward */), true /* isOutgoing */,
-            {{Segment(mwmId, 20, 2, false /* forward */), kEdgesWeight}});
+            {{Segment(mwmId, 20, 2, false /* forward */),
+              RouteWeight::FromCrossMwmWeight(kEdgesWeight)}});
 
   TestEdges(connector, Segment(mwmId, 20, 2, true /* forward */), true /* isOutgoing */,
-            {{Segment(mwmId, 20, 2, false /* forward */), kEdgesWeight}});
+            {{Segment(mwmId, 20, 2, false /* forward */),
+              RouteWeight::FromCrossMwmWeight(kEdgesWeight)}});
 
-  TestEdges(connector, Segment(mwmId, 20, 2, false /* forward */), false /* isOutgoing */,
-            {{Segment(mwmId, 10, 1, true /* forward */), kEdgesWeight},
-             {Segment(mwmId, 20, 2, true /* forward */), kEdgesWeight}});
+  TestEdges(
+      connector, Segment(mwmId, 20, 2, false /* forward */), false /* isOutgoing */,
+      {{Segment(mwmId, 10, 1, true /* forward */), RouteWeight::FromCrossMwmWeight(kEdgesWeight)},
+       {Segment(mwmId, 20, 2, true /* forward */), RouteWeight::FromCrossMwmWeight(kEdgesWeight)}});
 }
 
 UNIT_TEST(WeightsSerialization)
 {
   size_t constexpr kNumTransitions = 3;
-  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)};
+  vector<double> const weights = {
+      4.0,  20.0, CrossMwmConnector::kNoRoute, 12.0, CrossMwmConnector::kNoRoute, 40.0, 48.0,
+      24.0, 12.0};
   TEST_EQUAL(weights.size(), kNumTransitions * kNumTransitions, ());
 
   vector<uint8_t> buffer;
@@ -311,10 +308,10 @@ UNIT_TEST(WeightsSerialization)
     for (uint32_t exitId = 0; exitId < kNumTransitions; ++exitId)
     {
       auto const weight = weights[weightIdx];
-      if (weight != RouteWeight(CrossMwmConnector::kNoRoute))
+      if (weight != CrossMwmConnector::kNoRoute)
       {
         expectedEdges.emplace_back(Segment(mwmId, exitId, 1 /* segmentIdx */, false /* forward */),
-                                   weight);
+                                   RouteWeight::FromCrossMwmWeight(weight));
       }
       ++weightIdx;
     }
diff --git a/routing/routing_tests/index_graph_tools.cpp b/routing/routing_tests/index_graph_tools.cpp
index 7577f3748d..3cf02c754e 100644
--- a/routing/routing_tests/index_graph_tools.cpp
+++ b/routing/routing_tests/index_graph_tools.cpp
@@ -2,6 +2,8 @@
 
 #include "testing/testing.hpp"
 
+#include "routing/base/routing_result.hpp"
+
 #include "routing_common/car_model.hpp"
 
 #include "base/assert.hpp"
@@ -21,11 +23,12 @@ void TestGeometryLoader::Load(uint32_t featureId, RoadGeometry & road)
 }
 
 void TestGeometryLoader::AddRoad(uint32_t featureId, bool oneWay, float speed,
-                                 RoadGeometry::Points const & points)
+                                 RoadGeometry::Points const & points, bool transitAllowed)
 {
   auto it = m_roads.find(featureId);
   CHECK(it == m_roads.end(), ("Already contains feature", featureId));
   m_roads[featureId] = RoadGeometry(oneWay, speed, points);
+  m_roads[featureId].SetTransitAllowedForTests(transitAllowed);
 }
 
 // ZeroGeometryLoader ------------------------------------------------------------------------------
@@ -287,6 +290,9 @@ AStarAlgorithm<IndexGraphStarter>::Result CalculateRoute(IndexGraphStarter & sta
       starter, starter.GetStartSegment(), starter.GetFinishSegment(), routingResult,
       {} /* cancellable */, {} /* onVisitedVertexCallback */);
 
+  if (!starter.CheckRoutingResultMeetsRestrictions(routingResult))
+    resultCode == AStarAlgorithm<IndexGraphStarter>::Result::NoPath;
+
   timeSec = routingResult.distance.GetWeight();
   roadPoints = routingResult.path;
   return resultCode;
diff --git a/routing/routing_tests/index_graph_tools.hpp b/routing/routing_tests/index_graph_tools.hpp
index 946b885070..520411a7df 100644
--- a/routing/routing_tests/index_graph_tools.hpp
+++ b/routing/routing_tests/index_graph_tools.hpp
@@ -62,7 +62,7 @@ public:
   void Load(uint32_t featureId, routing::RoadGeometry & road) override;
 
   void AddRoad(uint32_t featureId, bool oneWay, float speed,
-               routing::RoadGeometry::Points const & points);
+               routing::RoadGeometry::Points const & points, bool transitAllowed = true);
 
 private:
   unordered_map<uint32_t, routing::RoadGeometry> m_roads;
diff --git a/routing/routing_tests/restriction_test.cpp b/routing/routing_tests/restriction_test.cpp
index 012cf7ecaa..e1e3a12089 100644
--- a/routing/routing_tests/restriction_test.cpp
+++ b/routing/routing_tests/restriction_test.cpp
@@ -896,4 +896,97 @@ UNIT_CLASS_TEST(RestrictionTest, FGraph_RestrictionF0F2Only)
                                                  m2::PointD(1, 1), *m_graph),
       move(restrictions), *this);
 }
+
+//                  *---F4---*
+//                  |        |
+//                 F3        F5
+//                  |        |
+// 0 Start *---F0---*---F1---*---F2---* Finish
+//         0        1        2        3
+unique_ptr<WorldGraph> BuildNontransitGraph(bool transitStart, bool transitShortWay,
+                                            bool transitLongWay)
+{
+  unique_ptr<TestGeometryLoader> loader = make_unique<TestGeometryLoader>();
+  loader->AddRoad(0 /* feature id */, false /* one way */, 1.0 /* speed */,
+                  RoadGeometry::Points({{0.0, 0.0}, {1.0, 0.0}}),
+                  transitStart /* transitAllowed */);
+  loader->AddRoad(1 /* feature id */, false /* one way */, 1.0 /* speed */,
+                  RoadGeometry::Points({{1.0, 0.0}, {2.0, 0.0}}),
+                  transitShortWay /* transitAllowed */);
+  loader->AddRoad(2 /* feature id */, false /* one way */, 1.0 /* speed */,
+                  RoadGeometry::Points({{2.0, 0.0}, {3.0, 0.0}}), true /* transitAllowed */);
+  loader->AddRoad(3 /* feature id */, false /* one way */, 1.0 /* speed */,
+                  RoadGeometry::Points({{1.0, 0.0}, {1.0, 1.0}}), true /* transitAllowed */);
+  loader->AddRoad(4 /* feature id */, false /* one way */, 1.0 /* speed */,
+                  RoadGeometry::Points({{1.0, 1.0}, {2.0, 1.0}}),
+                  transitLongWay /* transitAllowed */);
+  loader->AddRoad(5 /* feature id */, false /* one way */, 1.0 /* speed */,
+                  RoadGeometry::Points({{2.0, 1.0}, {2.0, 0.0}}), true /* transitAllowed */);
+
+  vector<Joint> const joints = {
+      MakeJoint({{0 /* feature id */, 0 /* point id */}}), /* joint at point (0, 0) */
+      MakeJoint({{0, 1}, {1, 0}, {3, 0}}),                 /* joint at point (1, 0) */
+      MakeJoint({{1, 1}, {2, 0}, {5, 1}}),                 /* joint at point (2, 0) */
+      MakeJoint({{3, 1}, {4, 0}}),                         /* joint at point (1, 1) */
+      MakeJoint({{4, 1}, {5, 0}}),                         /* joint at point (2, 1) */
+      MakeJoint({{2, 1}}),                                 /* joint at point (3, 0) */
+  };
+
+  traffic::TrafficCache const trafficCache;
+  shared_ptr<EdgeEstimator> estimator = CreateEstimatorForCar(trafficCache);
+  return BuildWorldGraph(move(loader), estimator, joints);
+}
+
+UNIT_CLASS_TEST(RestrictionTest, NontransitStart)
+{
+  Init(BuildNontransitGraph(false /* transitStart */, true /* transitShortWay */,
+                            true /* transitLongWay */));
+  vector<m2::PointD> const expectedGeom = {{0 /* x */, 0 /* y */}, {1, 0}, {2, 0}, {3, 0}};
+
+  SetStarter(routing::IndexGraphStarter::MakeFakeEnding(
+                 Segment(kTestNumMwmId, 0, 0, true /* forward */), m2::PointD(0, 0), *m_graph),
+             routing::IndexGraphStarter::MakeFakeEnding(
+                 Segment(kTestNumMwmId, 2, 0, true /* forward */), m2::PointD(3, 0), *m_graph));
+  TestRouteGeometry(*m_starter, AStarAlgorithm<IndexGraphStarter>::Result::OK, expectedGeom);
+}
+
+UNIT_CLASS_TEST(RestrictionTest, NontransitShortWay)
+{
+  Init(BuildNontransitGraph(true /* transitStart */, false /* transitShortWay */,
+                            true /* transitLongWay */));
+  vector<m2::PointD> const expectedGeom = {
+      {0 /* x */, 0 /* y */}, {1, 0}, {1, 1}, {2, 1}, {2, 0}, {3, 0}};
+
+  SetStarter(routing::IndexGraphStarter::MakeFakeEnding(
+                 Segment(kTestNumMwmId, 0, 0, true /* forward */), m2::PointD(0, 0), *m_graph),
+             routing::IndexGraphStarter::MakeFakeEnding(
+                 Segment(kTestNumMwmId, 2, 0, true /* forward */), m2::PointD(3, 0), *m_graph));
+  TestRouteGeometry(*m_starter, AStarAlgorithm<IndexGraphStarter>::Result::OK, expectedGeom);
+}
+
+UNIT_CLASS_TEST(RestrictionTest, NontransitWay)
+{
+  Init(BuildNontransitGraph(true /* transitStart */, false /* transitShortWay */,
+                            false /* transitLongWay */));
+
+  SetStarter(routing::IndexGraphStarter::MakeFakeEnding(
+                 Segment(kTestNumMwmId, 0, 0, true /* forward */), m2::PointD(0, 0), *m_graph),
+             routing::IndexGraphStarter::MakeFakeEnding(
+                 Segment(kTestNumMwmId, 2, 0, true /* forward */), m2::PointD(3, 0), *m_graph));
+  TestRouteGeometry(*m_starter, AStarAlgorithm<IndexGraphStarter>::Result::NoPath, {});
+}
+
+UNIT_CLASS_TEST(RestrictionTest, NontransiStartAndShortWay)
+{
+  Init(BuildNontransitGraph(false /* transitStart */, false /* transitShortWay */,
+                            true /* transitLongWay */));
+  // We can get F1 because F0 is in the same nontransit area/
+  vector<m2::PointD> const expectedGeom = {{0 /* x */, 0 /* y */}, {1, 0}, {2, 0}, {3, 0}};
+
+  SetStarter(routing::IndexGraphStarter::MakeFakeEnding(
+                 Segment(kTestNumMwmId, 0, 0, true /* forward */), m2::PointD(0, 0), *m_graph),
+             routing::IndexGraphStarter::MakeFakeEnding(
+                 Segment(kTestNumMwmId, 2, 0, true /* forward */), m2::PointD(3, 0), *m_graph));
+  TestRouteGeometry(*m_starter, AStarAlgorithm<IndexGraphStarter>::Result::OK, expectedGeom);
+}
 }  // namespace routing_test
diff --git a/routing/world_graph.cpp b/routing/world_graph.cpp
index 16397dde50..976ce62a4d 100644
--- a/routing/world_graph.cpp
+++ b/routing/world_graph.cpp
@@ -63,7 +63,8 @@ void WorldGraph::GetIngoingEdgesList(Segment const & segment, vector<SegmentEdge
 RouteWeight WorldGraph::HeuristicCostEstimate(Segment const & from, Segment const & to)
 {
   return RouteWeight(
-      m_estimator->CalcHeuristic(GetPoint(from, true /* front */), GetPoint(to, true /* front */)));
+      m_estimator->CalcHeuristic(GetPoint(from, true /* front */), GetPoint(to, true /* front */)),
+      0);
 }
 
 void WorldGraph::GetTwins(Segment const & segment, bool isOutgoing, vector<SegmentEdge> & edges)
@@ -75,7 +76,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, RouteWeight(weight));
+    edges.emplace_back(twin, RouteWeight(weight, 0));
   }
 }
 
diff --git a/xcode/routing/routing.xcodeproj/project.pbxproj b/xcode/routing/routing.xcodeproj/project.pbxproj
index b017aa98cd..8a13e2944f 100644
--- a/xcode/routing/routing.xcodeproj/project.pbxproj
+++ b/xcode/routing/routing.xcodeproj/project.pbxproj
@@ -56,6 +56,7 @@
 		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 */; };
+		405F48DC1F6AD01C005BA81A /* routing_result.hpp in Headers */ = {isa = PBXBuildFile; fileRef = 405F48DB1F6AD01C005BA81A /* routing_result.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 */; };
@@ -338,6 +339,7 @@
 		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>"; };
+		405F48DB1F6AD01C005BA81A /* routing_result.hpp */ = {isa = PBXFileReference; fileEncoding = 4; lastKnownFileType = sourcecode.cpp.h; path = routing_result.hpp; 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>"; };
@@ -640,6 +642,7 @@
 				671F58BC1B874EC80032311E /* followed_polyline.hpp */,
 				A1616E2D1B6B60B3003F078E /* astar_progress.hpp */,
 				A120B3521B4A7C1C002F3808 /* astar_algorithm.hpp */,
+				405F48DB1F6AD01C005BA81A /* routing_result.hpp */,
 			);
 			path = base;
 			sourceTree = "<group>";
@@ -1002,6 +1005,7 @@
 				A120B3511B4A7C0A002F3808 /* routing_algorithm.hpp in Headers */,
 				0C5FEC6B1DDE193F0017688C /* road_point.hpp in Headers */,
 				56099E2B1CC7C97D00A7772A /* turn_candidate.hpp in Headers */,
+				405F48DC1F6AD01C005BA81A /* routing_result.hpp in Headers */,
 				56C4392D1E93E5DF00998E29 /* transition_points.hpp in Headers */,
 				0C5FEC551DDE191E0017688C /* edge_estimator.hpp in Headers */,
 				670B84C11A9381D900CE4492 /* cross_routing_context.hpp in Headers */,