src/graph/sp/bm/lib.hpp - GCC Code Coverage Report

Directory:	./
Coverage:	low: ≥ 0% medium: ≥ 75.0% high: ≥ 90.0%

	Coverage	Exec / Excl / Total
Lines:	100.0%	68 / 0 / 68
Functions:	100.0%	8 / 0 / 8
Branches:	96.3%	79 / 0 / 82

    src/graph/sp/bm/lib.hpp
    
        Line
        Branch
        Exec
        Source
      
        #pragma once
      
        #include "../../../math/iroot/sqrt/lib.hpp"
      
        #include "../../../util/alias/others/lib.hpp"
      
        #include "../../../util/traits/math/lib.hpp"
      
        #include "../../ds/graph_c/lib.hpp"
      
        namespace tifa_libs {
      
        // cb_relax(now, to)
      
        // @return false if negative cycle detected
      
        template <wgraph_c G, class F>
      
        requires(!uint_c<TPN G::Et>) && requires(F relex, u32 now, u32 to) { relex(now, to); }
      
        581687
        bool bellman_ford(G CR g, u32 s, F&& cb_relax, vec<TPN G::Et>& dis) NE {
      
        581687
          cu32 n = g.vsize(), sn = isqrt(n);
      
          3/6bool tifa_libs::bellman_ford<tifa_libs::graph_impl_::graph<tifa_libs::alist_impl_::alist_tag<double> >, tifa_libs::fn_0::{lambda((auto:1&&)...)#1} const&>(tifa_libs::graph_impl_::graph<tifa_libs::alist_impl_::alist_tag<double> > const&, unsigned int, tifa_libs::fn_0::{lambda((auto:1&&)...)#1} const&, std::vector<tifa_libs::graph_impl_::graph<tifa_libs::alist_impl_::alist_tag<double> >::Et, std::allocator<tifa_libs::graph_impl_::graph<tifa_libs::alist_impl_::alist_tag<double> >::Et> >&):
✗ Branch 1 not taken.
✓ Branch 2 taken 581597 times.
bool tifa_libs::bellman_ford<tifa_libs::graph_impl_::graph<tifa_libs::alist_impl_::alist_tag<int> >, tifa_libs::fn_0::{lambda((auto:1&&)...)#1} const&>(tifa_libs::graph_impl_::graph<tifa_libs::alist_impl_::alist_tag<int> > const&, unsigned int, tifa_libs::fn_0::{lambda((auto:1&&)...)#1} const&, std::vector<tifa_libs::graph_impl_::graph<tifa_libs::alist_impl_::alist_tag<int> >::Et, std::allocator<tifa_libs::graph_impl_::graph<tifa_libs::alist_impl_::alist_tag<int> >::Et> >&):
✗ Branch 1 not taken.
✓ Branch 2 taken 40 times.
bool tifa_libs::bellman_ford<tifa_libs::graph_impl_::graph<tifa_libs::alist_impl_::alist_tag<long> >, tifa_libs::fn_0::{lambda((auto:1&&)...)#1} const&>(tifa_libs::graph_impl_::graph<tifa_libs::alist_impl_::alist_tag<long> > const&, unsigned int, tifa_libs::fn_0::{lambda((auto:1&&)...)#1} const&, std::vector<tifa_libs::graph_impl_::graph<tifa_libs::alist_impl_::alist_tag<long> >::Et, std::allocator<tifa_libs::graph_impl_::graph<tifa_libs::alist_impl_::alist_tag<long> >::Et> >&):
✗ Branch 1 not taken.
✓ Branch 2 taken 50 times.

        581687
          assert(dis.size() == n);
      
        1163374
          vecb vis(n);
      
        1163374
          vecu dep(n);
      
        581687
          std::deque<u32> q({s});
      
        387867977
          auto upd_q = [&] {
      
          18/18tifa_libs::bellman_ford<tifa_libs::graph_impl_::graph<tifa_libs::alist_impl_::alist_tag<double> >, tifa_libs::fn_0::{lambda((auto:1&&)...)#1} const&>(tifa_libs::graph_impl_::graph<tifa_libs::alist_impl_::alist_tag<double> > const&, unsigned int, tifa_libs::fn_0::{lambda((auto:1&&)...)#1} const&, std::vector<tifa_libs::graph_impl_::graph<tifa_libs::alist_impl_::alist_tag<double> >::Et, std::allocator<tifa_libs::graph_impl_::graph<tifa_libs::alist_impl_::alist_tag<double> >::Et> >&)::{lambda()#1}::operator()() const:
✓ Branch 1 taken 191267569 times.
✓ Branch 2 taken 2312044 times.
✓ Branch 7 taken 18976106 times.
✓ Branch 8 taken 172291463 times.
✓ Branch 9 taken 18976106 times.
✓ Branch 10 taken 174603507 times.
tifa_libs::bellman_ford<tifa_libs::graph_impl_::graph<tifa_libs::alist_impl_::alist_tag<int> >, tifa_libs::fn_0::{lambda((auto:1&&)...)#1} const&>(tifa_libs::graph_impl_::graph<tifa_libs::alist_impl_::alist_tag<int> > const&, unsigned int, tifa_libs::fn_0::{lambda((auto:1&&)...)#1} const&, std::vector<tifa_libs::graph_impl_::graph<tifa_libs::alist_impl_::alist_tag<int> >::Et, std::allocator<tifa_libs::graph_impl_::graph<tifa_libs::alist_impl_::alist_tag<int> >::Et> >&)::{lambda()#1}::operator()() const:
✓ Branch 1 taken 51341 times.
✓ Branch 2 taken 702 times.
✓ Branch 7 taken 1271 times.
✓ Branch 8 taken 50070 times.
✓ Branch 9 taken 1271 times.
✓ Branch 10 taken 50772 times.
tifa_libs::bellman_ford<tifa_libs::graph_impl_::graph<tifa_libs::alist_impl_::alist_tag<long> >, tifa_libs::fn_0::{lambda((auto:1&&)...)#1} const&>(tifa_libs::graph_impl_::graph<tifa_libs::alist_impl_::alist_tag<long> > const&, unsigned int, tifa_libs::fn_0::{lambda((auto:1&&)...)#1} const&, std::vector<tifa_libs::graph_impl_::graph<tifa_libs::alist_impl_::alist_tag<long> >::Et, std::allocator<tifa_libs::graph_impl_::graph<tifa_libs::alist_impl_::alist_tag<long> >::Et> >&)::{lambda()#1}::operator()() const:
✓ Branch 1 taken 11197 times.
✓ Branch 2 taken 292 times.
✓ Branch 7 taken 827 times.
✓ Branch 8 taken 10370 times.
✓ Branch 9 taken 827 times.
✓ Branch 10 taken 10662 times.

        193643145
            if (q.size() >= 2 && dis[q.front()] > dis[q.back()]) swap(q.front(), q.back());
      
          };
      
        581687
          dis[s] = 0, vis[s] = true, dep[s] = 1;
      
          6/6tifa_libs::bellman_ford<tifa_libs::graph_impl_::graph<tifa_libs::alist_impl_::alist_tag<double> >, tifa_libs::fn_0::{lambda((auto:1&&)...)#1} const&>(tifa_libs::graph_impl_::graph<tifa_libs::alist_impl_::alist_tag<double> > const&, unsigned int, tifa_libs::fn_0::{lambda((auto:1&&)...)#1} const&, std::vector<tifa_libs::graph_impl_::graph<tifa_libs::alist_impl_::alist_tag<double> >::Et, std::allocator<tifa_libs::graph_impl_::graph<tifa_libs::alist_impl_::alist_tag<double> >::Et> >&)::{lambda()#1}::operator()() const:
✓ Branch 1 taken 97058438 times.
✓ Branch 2 taken 581275 times.
tifa_libs::bellman_ford<tifa_libs::graph_impl_::graph<tifa_libs::alist_impl_::alist_tag<int> >, tifa_libs::fn_0::{lambda((auto:1&&)...)#1} const&>(tifa_libs::graph_impl_::graph<tifa_libs::alist_impl_::alist_tag<int> > const&, unsigned int, tifa_libs::fn_0::{lambda((auto:1&&)...)#1} const&, std::vector<tifa_libs::graph_impl_::graph<tifa_libs::alist_impl_::alist_tag<int> >::Et, std::allocator<tifa_libs::graph_impl_::graph<tifa_libs::alist_impl_::alist_tag<int> >::Et> >&)::{lambda()#1}::operator()() const:
✓ Branch 1 taken 25994 times.
✓ Branch 2 taken 31 times.
tifa_libs::bellman_ford<tifa_libs::graph_impl_::graph<tifa_libs::alist_impl_::alist_tag<long> >, tifa_libs::fn_0::{lambda((auto:1&&)...)#1} const&>(tifa_libs::graph_impl_::graph<tifa_libs::alist_impl_::alist_tag<long> > const&, unsigned int, tifa_libs::fn_0::{lambda((auto:1&&)...)#1} const&, std::vector<tifa_libs::graph_impl_::graph<tifa_libs::alist_impl_::alist_tag<long> >::Et, std::allocator<tifa_libs::graph_impl_::graph<tifa_libs::alist_impl_::alist_tag<long> >::Et> >&)::{lambda()#1}::operator()() const:
✓ Branch 1 taken 5720 times.
✓ Branch 2 taken 43 times.

        97671501
          while (!q.empty()) {
      
        97090152
            cu32 u = q.front();
      
          6/6tifa_libs::bellman_ford<tifa_libs::graph_impl_::graph<tifa_libs::alist_impl_::alist_tag<double> >, tifa_libs::fn_0::{lambda((auto:1&&)...)#1} const&>(tifa_libs::graph_impl_::graph<tifa_libs::alist_impl_::alist_tag<double> > const&, unsigned int, tifa_libs::fn_0::{lambda((auto:1&&)...)#1} const&, std::vector<tifa_libs::graph_impl_::graph<tifa_libs::alist_impl_::alist_tag<double> >::Et, std::allocator<tifa_libs::graph_impl_::graph<tifa_libs::alist_impl_::alist_tag<double> >::Et> >&)::{lambda()#1}::operator()() const:
✓ Branch 10 taken 326165913 times.
✓ Branch 11 taken 97058116 times.
tifa_libs::bellman_ford<tifa_libs::graph_impl_::graph<tifa_libs::alist_impl_::alist_tag<int> >, tifa_libs::fn_0::{lambda((auto:1&&)...)#1} const&>(tifa_libs::graph_impl_::graph<tifa_libs::alist_impl_::alist_tag<int> > const&, unsigned int, tifa_libs::fn_0::{lambda((auto:1&&)...)#1} const&, std::vector<tifa_libs::graph_impl_::graph<tifa_libs::alist_impl_::alist_tag<int> >::Et, std::allocator<tifa_libs::graph_impl_::graph<tifa_libs::alist_impl_::alist_tag<int> >::Et> >&)::{lambda()#1}::operator()() const:
✓ Branch 10 taken 43647 times.
✓ Branch 11 taken 25985 times.
tifa_libs::bellman_ford<tifa_libs::graph_impl_::graph<tifa_libs::alist_impl_::alist_tag<long> >, tifa_libs::fn_0::{lambda((auto:1&&)...)#1} const&>(tifa_libs::graph_impl_::graph<tifa_libs::alist_impl_::alist_tag<long> > const&, unsigned int, tifa_libs::fn_0::{lambda((auto:1&&)...)#1} const&, std::vector<tifa_libs::graph_impl_::graph<tifa_libs::alist_impl_::alist_tag<long> >::Et, std::allocator<tifa_libs::graph_impl_::graph<tifa_libs::alist_impl_::alist_tag<long> >::Et> >&)::{lambda()#1}::operator()() const:
✓ Branch 10 taken 52529 times.
✓ Branch 11 taken 5713 times.

        423351903
            for (q.pop_front(), upd_q(), vis[u] = false; auto [v, w] : g[u])
      
          6/6tifa_libs::bellman_ford<tifa_libs::graph_impl_::graph<tifa_libs::alist_impl_::alist_tag<double> >, tifa_libs::fn_0::{lambda((auto:1&&)...)#1} const&>(tifa_libs::graph_impl_::graph<tifa_libs::alist_impl_::alist_tag<double> > const&, unsigned int, tifa_libs::fn_0::{lambda((auto:1&&)...)#1} const&, std::vector<tifa_libs::graph_impl_::graph<tifa_libs::alist_impl_::alist_tag<double> >::Et, std::allocator<tifa_libs::graph_impl_::graph<tifa_libs::alist_impl_::alist_tag<double> >::Et> >&)::{lambda()#1}::operator()() const:
✓ Branch 2 taken 110196134 times.
✓ Branch 3 taken 215969779 times.
tifa_libs::bellman_ford<tifa_libs::graph_impl_::graph<tifa_libs::alist_impl_::alist_tag<int> >, tifa_libs::fn_0::{lambda((auto:1&&)...)#1} const&>(tifa_libs::graph_impl_::graph<tifa_libs::alist_impl_::alist_tag<int> > const&, unsigned int, tifa_libs::fn_0::{lambda((auto:1&&)...)#1} const&, std::vector<tifa_libs::graph_impl_::graph<tifa_libs::alist_impl_::alist_tag<int> >::Et, std::allocator<tifa_libs::graph_impl_::graph<tifa_libs::alist_impl_::alist_tag<int> >::Et> >&)::{lambda()#1}::operator()() const:
✓ Branch 2 taken 36928 times.
✓ Branch 3 taken 6719 times.
tifa_libs::bellman_ford<tifa_libs::graph_impl_::graph<tifa_libs::alist_impl_::alist_tag<long> >, tifa_libs::fn_0::{lambda((auto:1&&)...)#1} const&>(tifa_libs::graph_impl_::graph<tifa_libs::alist_impl_::alist_tag<long> > const&, unsigned int, tifa_libs::fn_0::{lambda((auto:1&&)...)#1} const&, std::vector<tifa_libs::graph_impl_::graph<tifa_libs::alist_impl_::alist_tag<long> >::Et, std::allocator<tifa_libs::graph_impl_::graph<tifa_libs::alist_impl_::alist_tag<long> >::Et> >&)::{lambda()#1}::operator()() const:
✓ Branch 2 taken 11316 times.
✓ Branch 3 taken 41213 times.

        326262089
              if (dis[u] + w < dis[v]) {
      
          6/6tifa_libs::bellman_ford<tifa_libs::graph_impl_::graph<tifa_libs::alist_impl_::alist_tag<double> >, tifa_libs::fn_0::{lambda((auto:1&&)...)#1} const&>(tifa_libs::graph_impl_::graph<tifa_libs::alist_impl_::alist_tag<double> > const&, unsigned int, tifa_libs::fn_0::{lambda((auto:1&&)...)#1} const&, std::vector<tifa_libs::graph_impl_::graph<tifa_libs::alist_impl_::alist_tag<double> >::Et, std::allocator<tifa_libs::graph_impl_::graph<tifa_libs::alist_impl_::alist_tag<double> >::Et> >&)::{lambda()#1}::operator()() const:
✓ Branch 5 taken 13674637 times.
✓ Branch 6 taken 96521497 times.
tifa_libs::bellman_ford<tifa_libs::graph_impl_::graph<tifa_libs::alist_impl_::alist_tag<int> >, tifa_libs::fn_0::{lambda((auto:1&&)...)#1} const&>(tifa_libs::graph_impl_::graph<tifa_libs::alist_impl_::alist_tag<int> > const&, unsigned int, tifa_libs::fn_0::{lambda((auto:1&&)...)#1} const&, std::vector<tifa_libs::graph_impl_::graph<tifa_libs::alist_impl_::alist_tag<int> >::Et, std::allocator<tifa_libs::graph_impl_::graph<tifa_libs::alist_impl_::alist_tag<int> >::Et> >&)::{lambda()#1}::operator()() const:
✓ Branch 5 taken 10870 times.
✓ Branch 6 taken 26058 times.
tifa_libs::bellman_ford<tifa_libs::graph_impl_::graph<tifa_libs::alist_impl_::alist_tag<long> >, tifa_libs::fn_0::{lambda((auto:1&&)...)#1} const&>(tifa_libs::graph_impl_::graph<tifa_libs::alist_impl_::alist_tag<long> > const&, unsigned int, tifa_libs::fn_0::{lambda((auto:1&&)...)#1} const&, std::vector<tifa_libs::graph_impl_::graph<tifa_libs::alist_impl_::alist_tag<long> >::Et, std::allocator<tifa_libs::graph_impl_::graph<tifa_libs::alist_impl_::alist_tag<long> >::Et> >&)::{lambda()#1}::operator()() const:
✓ Branch 5 taken 5540 times.
✓ Branch 6 taken 5776 times.

        110244378
                if (cb_relax(u, v), dis[v] = dis[u] + w; vis[v]) continue;
      
          6/6tifa_libs::bellman_ford<tifa_libs::graph_impl_::graph<tifa_libs::alist_impl_::alist_tag<double> >, tifa_libs::fn_0::{lambda((auto:1&&)...)#1} const&>(tifa_libs::graph_impl_::graph<tifa_libs::alist_impl_::alist_tag<double> > const&, unsigned int, tifa_libs::fn_0::{lambda((auto:1&&)...)#1} const&, std::vector<tifa_libs::graph_impl_::graph<tifa_libs::alist_impl_::alist_tag<double> >::Et, std::allocator<tifa_libs::graph_impl_::graph<tifa_libs::alist_impl_::alist_tag<double> >::Et> >&)::{lambda()#1}::operator()() const:
✓ Branch 1 taken 322 times.
✓ Branch 2 taken 96521175 times.
tifa_libs::bellman_ford<tifa_libs::graph_impl_::graph<tifa_libs::alist_impl_::alist_tag<int> >, tifa_libs::fn_0::{lambda((auto:1&&)...)#1} const&>(tifa_libs::graph_impl_::graph<tifa_libs::alist_impl_::alist_tag<int> > const&, unsigned int, tifa_libs::fn_0::{lambda((auto:1&&)...)#1} const&, std::vector<tifa_libs::graph_impl_::graph<tifa_libs::alist_impl_::alist_tag<int> >::Et, std::allocator<tifa_libs::graph_impl_::graph<tifa_libs::alist_impl_::alist_tag<int> >::Et> >&)::{lambda()#1}::operator()() const:
✓ Branch 1 taken 9 times.
✓ Branch 2 taken 26049 times.
tifa_libs::bellman_ford<tifa_libs::graph_impl_::graph<tifa_libs::alist_impl_::alist_tag<long> >, tifa_libs::fn_0::{lambda((auto:1&&)...)#1} const&>(tifa_libs::graph_impl_::graph<tifa_libs::alist_impl_::alist_tag<long> > const&, unsigned int, tifa_libs::fn_0::{lambda((auto:1&&)...)#1} const&, std::vector<tifa_libs::graph_impl_::graph<tifa_libs::alist_impl_::alist_tag<long> >::Et, std::allocator<tifa_libs::graph_impl_::graph<tifa_libs::alist_impl_::alist_tag<long> >::Et> >&)::{lambda()#1}::operator()() const:
✓ Branch 1 taken 7 times.
✓ Branch 2 taken 5769 times.

        96553331
                if (++dep[v] > n) return false;
      
        96552993
                vis[v] = true;
      
          24/24tifa_libs::bellman_ford<tifa_libs::graph_impl_::graph<tifa_libs::alist_impl_::alist_tag<double> >, tifa_libs::fn_0::{lambda((auto:1&&)...)#1} const&>(tifa_libs::graph_impl_::graph<tifa_libs::alist_impl_::alist_tag<double> > const&, unsigned int, tifa_libs::fn_0::{lambda((auto:1&&)...)#1} const&, std::vector<tifa_libs::graph_impl_::graph<tifa_libs::alist_impl_::alist_tag<double> >::Et, std::allocator<tifa_libs::graph_impl_::graph<tifa_libs::alist_impl_::alist_tag<double> >::Et> >&)::{lambda()#1}::operator()() const:
✓ Branch 1 taken 95918469 times.
✓ Branch 2 taken 602706 times.
✓ Branch 4 taken 92646052 times.
✓ Branch 5 taken 3272417 times.
✓ Branch 8 taken 92584794 times.
✓ Branch 9 taken 663964 times.
✓ Branch 12 taken 40148851 times.
✓ Branch 13 taken 53099907 times.
tifa_libs::bellman_ford<tifa_libs::graph_impl_::graph<tifa_libs::alist_impl_::alist_tag<int> >, tifa_libs::fn_0::{lambda((auto:1&&)...)#1} const&>(tifa_libs::graph_impl_::graph<tifa_libs::alist_impl_::alist_tag<int> > const&, unsigned int, tifa_libs::fn_0::{lambda((auto:1&&)...)#1} const&, std::vector<tifa_libs::graph_impl_::graph<tifa_libs::alist_impl_::alist_tag<int> >::Et, std::allocator<tifa_libs::graph_impl_::graph<tifa_libs::alist_impl_::alist_tag<int> >::Et> >&)::{lambda()#1}::operator()() const:
✓ Branch 1 taken 21431 times.
✓ Branch 2 taken 4618 times.
✓ Branch 4 taken 10700 times.
✓ Branch 5 taken 10731 times.
✓ Branch 8 taken 15108 times.
✓ Branch 9 taken 210 times.
✓ Branch 12 taken 13067 times.
✓ Branch 13 taken 2251 times.
tifa_libs::bellman_ford<tifa_libs::graph_impl_::graph<tifa_libs::alist_impl_::alist_tag<long> >, tifa_libs::fn_0::{lambda((auto:1&&)...)#1} const&>(tifa_libs::graph_impl_::graph<tifa_libs::alist_impl_::alist_tag<long> > const&, unsigned int, tifa_libs::fn_0::{lambda((auto:1&&)...)#1} const&, std::vector<tifa_libs::graph_impl_::graph<tifa_libs::alist_impl_::alist_tag<long> >::Et, std::allocator<tifa_libs::graph_impl_::graph<tifa_libs::alist_impl_::alist_tag<long> >::Et> >&)::{lambda()#1}::operator()() const:
✓ Branch 1 taken 3493 times.
✓ Branch 2 taken 2276 times.
✓ Branch 4 taken 2561 times.
✓ Branch 5 taken 932 times.
✓ Branch 8 taken 4768 times.
✓ Branch 9 taken 69 times.
✓ Branch 12 taken 1424 times.
✓ Branch 13 taken 3413 times.

        96552993
                (1 < dep[v] && dep[v] < sn) || dis[v] < TPN G::Et(q.size() ? dis[q.front()] : 0) ? q.push_front(v) : q.push_back(v);
      
        96552993
                upd_q();
      
              }
      
          }
      
        581349
          return true;
      
        581687
        }
      
        // cb_relax(now, to)
      
        template <wgraph_c G, class F>
      
        90
        auto bellman_ford(G CR g, u32 s, F&& cb_relax, TPN G::Et INF = std::numeric_limits<TPN G::Et>::max() / 2 - 1) NE {
      
        90
          std::optional ret{vec<TPN G::Et>(g.vsize(), INF)};
      
          4/4auto tifa_libs::bellman_ford<tifa_libs::graph_impl_::graph<tifa_libs::alist_impl_::alist_tag<int> >, tifa_libs::fn_0::{lambda((auto:1&&)...)#1} const&>(tifa_libs::graph_impl_::graph<tifa_libs::alist_impl_::alist_tag<int> > const&, unsigned int, tifa_libs::fn_0::{lambda((auto:1&&)...)#1} const&, tifa_libs::graph_impl_::graph<tifa_libs::alist_impl_::alist_tag<int> >::Et):
✓ Branch 3 taken 9 times.
✓ Branch 4 taken 31 times.
auto tifa_libs::bellman_ford<tifa_libs::graph_impl_::graph<tifa_libs::alist_impl_::alist_tag<long> >, tifa_libs::fn_0::{lambda((auto:1&&)...)#1} const&>(tifa_libs::graph_impl_::graph<tifa_libs::alist_impl_::alist_tag<long> > const&, unsigned int, tifa_libs::fn_0::{lambda((auto:1&&)...)#1} const&, tifa_libs::graph_impl_::graph<tifa_libs::alist_impl_::alist_tag<long> >::Et):
✓ Branch 3 taken 7 times.
✓ Branch 4 taken 43 times.

        90
          if (!bellman_ford(g, s, std::forward<F>(cb_relax), ret.value())) ret = std::nullopt;
      
        90
          return ret;
      
        }
      
        }  // namespace tifa_libs

Line	Branch	Exec	Source
1			#pragma once
2
3			#include "../../../math/iroot/sqrt/lib.hpp"
4			#include "../../../util/alias/others/lib.hpp"
5			#include "../../../util/traits/math/lib.hpp"
6			#include "../../ds/graph_c/lib.hpp"
7
8			namespace tifa_libs {
9
10			// cb_relax(now, to)
11			// @return false if negative cycle detected
12			template <wgraph_c G, class F>
13			requires(!uint_c<TPN G::Et>) && requires(F relex, u32 now, u32 to) { relex(now, to); }
14		581687	bool bellman_ford(G CR g, u32 s, F&& cb_relax, vec<TPN G::Et>& dis) NE {
15		581687	cu32 n = g.vsize(), sn = isqrt(n);
16	3/6 bool tifa_libs::bellman_ford<tifa_libs::graph_impl_::graph<tifa_libs::alist_impl_::alist_tag<double> >, tifa_libs::fn_0::{lambda((auto:1&&)...)#1} const&>(tifa_libs::graph_impl_::graph<tifa_libs::alist_impl_::alist_tag<double> > const&, unsigned int, tifa_libs::fn_0::{lambda((auto:1&&)...)#1} const&, std::vector<tifa_libs::graph_impl_::graph<tifa_libs::alist_impl_::alist_tag<double> >::Et, std::allocator<tifa_libs::graph_impl_::graph<tifa_libs::alist_impl_::alist_tag<double> >::Et> >&): ✗ Branch 1 not taken. ✓ Branch 2 taken 581597 times. bool tifa_libs::bellman_ford<tifa_libs::graph_impl_::graph<tifa_libs::alist_impl_::alist_tag<int> >, tifa_libs::fn_0::{lambda((auto:1&&)...)#1} const&>(tifa_libs::graph_impl_::graph<tifa_libs::alist_impl_::alist_tag<int> > const&, unsigned int, tifa_libs::fn_0::{lambda((auto:1&&)...)#1} const&, std::vector<tifa_libs::graph_impl_::graph<tifa_libs::alist_impl_::alist_tag<int> >::Et, std::allocator<tifa_libs::graph_impl_::graph<tifa_libs::alist_impl_::alist_tag<int> >::Et> >&): ✗ Branch 1 not taken. ✓ Branch 2 taken 40 times. bool tifa_libs::bellman_ford<tifa_libs::graph_impl_::graph<tifa_libs::alist_impl_::alist_tag<long> >, tifa_libs::fn_0::{lambda((auto:1&&)...)#1} const&>(tifa_libs::graph_impl_::graph<tifa_libs::alist_impl_::alist_tag<long> > const&, unsigned int, tifa_libs::fn_0::{lambda((auto:1&&)...)#1} const&, std::vector<tifa_libs::graph_impl_::graph<tifa_libs::alist_impl_::alist_tag<long> >::Et, std::allocator<tifa_libs::graph_impl_::graph<tifa_libs::alist_impl_::alist_tag<long> >::Et> >&): ✗ Branch 1 not taken. ✓ Branch 2 taken 50 times.	581687	assert(dis.size() == n);
17		1163374	vecb vis(n);
18		1163374	vecu dep(n);
19		581687	std::deque<u32> q({s});
20		387867977	auto upd_q = [&] {
21	18/18 tifa_libs::bellman_ford<tifa_libs::graph_impl_::graph<tifa_libs::alist_impl_::alist_tag<double> >, tifa_libs::fn_0::{lambda((auto:1&&)...)#1} const&>(tifa_libs::graph_impl_::graph<tifa_libs::alist_impl_::alist_tag<double> > const&, unsigned int, tifa_libs::fn_0::{lambda((auto:1&&)...)#1} const&, std::vector<tifa_libs::graph_impl_::graph<tifa_libs::alist_impl_::alist_tag<double> >::Et, std::allocator<tifa_libs::graph_impl_::graph<tifa_libs::alist_impl_::alist_tag<double> >::Et> >&)::{lambda()#1}::operator()() const: ✓ Branch 1 taken 191267569 times. ✓ Branch 2 taken 2312044 times. ✓ Branch 7 taken 18976106 times. ✓ Branch 8 taken 172291463 times. ✓ Branch 9 taken 18976106 times. ✓ Branch 10 taken 174603507 times. tifa_libs::bellman_ford<tifa_libs::graph_impl_::graph<tifa_libs::alist_impl_::alist_tag<int> >, tifa_libs::fn_0::{lambda((auto:1&&)...)#1} const&>(tifa_libs::graph_impl_::graph<tifa_libs::alist_impl_::alist_tag<int> > const&, unsigned int, tifa_libs::fn_0::{lambda((auto:1&&)...)#1} const&, std::vector<tifa_libs::graph_impl_::graph<tifa_libs::alist_impl_::alist_tag<int> >::Et, std::allocator<tifa_libs::graph_impl_::graph<tifa_libs::alist_impl_::alist_tag<int> >::Et> >&)::{lambda()#1}::operator()() const: ✓ Branch 1 taken 51341 times. ✓ Branch 2 taken 702 times. ✓ Branch 7 taken 1271 times. ✓ Branch 8 taken 50070 times. ✓ Branch 9 taken 1271 times. ✓ Branch 10 taken 50772 times. tifa_libs::bellman_ford<tifa_libs::graph_impl_::graph<tifa_libs::alist_impl_::alist_tag<long> >, tifa_libs::fn_0::{lambda((auto:1&&)...)#1} const&>(tifa_libs::graph_impl_::graph<tifa_libs::alist_impl_::alist_tag<long> > const&, unsigned int, tifa_libs::fn_0::{lambda((auto:1&&)...)#1} const&, std::vector<tifa_libs::graph_impl_::graph<tifa_libs::alist_impl_::alist_tag<long> >::Et, std::allocator<tifa_libs::graph_impl_::graph<tifa_libs::alist_impl_::alist_tag<long> >::Et> >&)::{lambda()#1}::operator()() const: ✓ Branch 1 taken 11197 times. ✓ Branch 2 taken 292 times. ✓ Branch 7 taken 827 times. ✓ Branch 8 taken 10370 times. ✓ Branch 9 taken 827 times. ✓ Branch 10 taken 10662 times.	193643145	if (q.size() >= 2 && dis[q.front()] > dis[q.back()]) swap(q.front(), q.back());
22			};
23		581687	dis[s] = 0, vis[s] = true, dep[s] = 1;
24	6/6 tifa_libs::bellman_ford<tifa_libs::graph_impl_::graph<tifa_libs::alist_impl_::alist_tag<double> >, tifa_libs::fn_0::{lambda((auto:1&&)...)#1} const&>(tifa_libs::graph_impl_::graph<tifa_libs::alist_impl_::alist_tag<double> > const&, unsigned int, tifa_libs::fn_0::{lambda((auto:1&&)...)#1} const&, std::vector<tifa_libs::graph_impl_::graph<tifa_libs::alist_impl_::alist_tag<double> >::Et, std::allocator<tifa_libs::graph_impl_::graph<tifa_libs::alist_impl_::alist_tag<double> >::Et> >&)::{lambda()#1}::operator()() const: ✓ Branch 1 taken 97058438 times. ✓ Branch 2 taken 581275 times. tifa_libs::bellman_ford<tifa_libs::graph_impl_::graph<tifa_libs::alist_impl_::alist_tag<int> >, tifa_libs::fn_0::{lambda((auto:1&&)...)#1} const&>(tifa_libs::graph_impl_::graph<tifa_libs::alist_impl_::alist_tag<int> > const&, unsigned int, tifa_libs::fn_0::{lambda((auto:1&&)...)#1} const&, std::vector<tifa_libs::graph_impl_::graph<tifa_libs::alist_impl_::alist_tag<int> >::Et, std::allocator<tifa_libs::graph_impl_::graph<tifa_libs::alist_impl_::alist_tag<int> >::Et> >&)::{lambda()#1}::operator()() const: ✓ Branch 1 taken 25994 times. ✓ Branch 2 taken 31 times. tifa_libs::bellman_ford<tifa_libs::graph_impl_::graph<tifa_libs::alist_impl_::alist_tag<long> >, tifa_libs::fn_0::{lambda((auto:1&&)...)#1} const&>(tifa_libs::graph_impl_::graph<tifa_libs::alist_impl_::alist_tag<long> > const&, unsigned int, tifa_libs::fn_0::{lambda((auto:1&&)...)#1} const&, std::vector<tifa_libs::graph_impl_::graph<tifa_libs::alist_impl_::alist_tag<long> >::Et, std::allocator<tifa_libs::graph_impl_::graph<tifa_libs::alist_impl_::alist_tag<long> >::Et> >&)::{lambda()#1}::operator()() const: ✓ Branch 1 taken 5720 times. ✓ Branch 2 taken 43 times.	97671501	while (!q.empty()) {
25		97090152	cu32 u = q.front();
26	6/6 tifa_libs::bellman_ford<tifa_libs::graph_impl_::graph<tifa_libs::alist_impl_::alist_tag<double> >, tifa_libs::fn_0::{lambda((auto:1&&)...)#1} const&>(tifa_libs::graph_impl_::graph<tifa_libs::alist_impl_::alist_tag<double> > const&, unsigned int, tifa_libs::fn_0::{lambda((auto:1&&)...)#1} const&, std::vector<tifa_libs::graph_impl_::graph<tifa_libs::alist_impl_::alist_tag<double> >::Et, std::allocator<tifa_libs::graph_impl_::graph<tifa_libs::alist_impl_::alist_tag<double> >::Et> >&)::{lambda()#1}::operator()() const: ✓ Branch 10 taken 326165913 times. ✓ Branch 11 taken 97058116 times. tifa_libs::bellman_ford<tifa_libs::graph_impl_::graph<tifa_libs::alist_impl_::alist_tag<int> >, tifa_libs::fn_0::{lambda((auto:1&&)...)#1} const&>(tifa_libs::graph_impl_::graph<tifa_libs::alist_impl_::alist_tag<int> > const&, unsigned int, tifa_libs::fn_0::{lambda((auto:1&&)...)#1} const&, std::vector<tifa_libs::graph_impl_::graph<tifa_libs::alist_impl_::alist_tag<int> >::Et, std::allocator<tifa_libs::graph_impl_::graph<tifa_libs::alist_impl_::alist_tag<int> >::Et> >&)::{lambda()#1}::operator()() const: ✓ Branch 10 taken 43647 times. ✓ Branch 11 taken 25985 times. tifa_libs::bellman_ford<tifa_libs::graph_impl_::graph<tifa_libs::alist_impl_::alist_tag<long> >, tifa_libs::fn_0::{lambda((auto:1&&)...)#1} const&>(tifa_libs::graph_impl_::graph<tifa_libs::alist_impl_::alist_tag<long> > const&, unsigned int, tifa_libs::fn_0::{lambda((auto:1&&)...)#1} const&, std::vector<tifa_libs::graph_impl_::graph<tifa_libs::alist_impl_::alist_tag<long> >::Et, std::allocator<tifa_libs::graph_impl_::graph<tifa_libs::alist_impl_::alist_tag<long> >::Et> >&)::{lambda()#1}::operator()() const: ✓ Branch 10 taken 52529 times. ✓ Branch 11 taken 5713 times.	423351903	for (q.pop_front(), upd_q(), vis[u] = false; auto [v, w] : g[u])
27	6/6 tifa_libs::bellman_ford<tifa_libs::graph_impl_::graph<tifa_libs::alist_impl_::alist_tag<double> >, tifa_libs::fn_0::{lambda((auto:1&&)...)#1} const&>(tifa_libs::graph_impl_::graph<tifa_libs::alist_impl_::alist_tag<double> > const&, unsigned int, tifa_libs::fn_0::{lambda((auto:1&&)...)#1} const&, std::vector<tifa_libs::graph_impl_::graph<tifa_libs::alist_impl_::alist_tag<double> >::Et, std::allocator<tifa_libs::graph_impl_::graph<tifa_libs::alist_impl_::alist_tag<double> >::Et> >&)::{lambda()#1}::operator()() const: ✓ Branch 2 taken 110196134 times. ✓ Branch 3 taken 215969779 times. tifa_libs::bellman_ford<tifa_libs::graph_impl_::graph<tifa_libs::alist_impl_::alist_tag<int> >, tifa_libs::fn_0::{lambda((auto:1&&)...)#1} const&>(tifa_libs::graph_impl_::graph<tifa_libs::alist_impl_::alist_tag<int> > const&, unsigned int, tifa_libs::fn_0::{lambda((auto:1&&)...)#1} const&, std::vector<tifa_libs::graph_impl_::graph<tifa_libs::alist_impl_::alist_tag<int> >::Et, std::allocator<tifa_libs::graph_impl_::graph<tifa_libs::alist_impl_::alist_tag<int> >::Et> >&)::{lambda()#1}::operator()() const: ✓ Branch 2 taken 36928 times. ✓ Branch 3 taken 6719 times. tifa_libs::bellman_ford<tifa_libs::graph_impl_::graph<tifa_libs::alist_impl_::alist_tag<long> >, tifa_libs::fn_0::{lambda((auto:1&&)...)#1} const&>(tifa_libs::graph_impl_::graph<tifa_libs::alist_impl_::alist_tag<long> > const&, unsigned int, tifa_libs::fn_0::{lambda((auto:1&&)...)#1} const&, std::vector<tifa_libs::graph_impl_::graph<tifa_libs::alist_impl_::alist_tag<long> >::Et, std::allocator<tifa_libs::graph_impl_::graph<tifa_libs::alist_impl_::alist_tag<long> >::Et> >&)::{lambda()#1}::operator()() const: ✓ Branch 2 taken 11316 times. ✓ Branch 3 taken 41213 times.	326262089	if (dis[u] + w < dis[v]) {
28	6/6 tifa_libs::bellman_ford<tifa_libs::graph_impl_::graph<tifa_libs::alist_impl_::alist_tag<double> >, tifa_libs::fn_0::{lambda((auto:1&&)...)#1} const&>(tifa_libs::graph_impl_::graph<tifa_libs::alist_impl_::alist_tag<double> > const&, unsigned int, tifa_libs::fn_0::{lambda((auto:1&&)...)#1} const&, std::vector<tifa_libs::graph_impl_::graph<tifa_libs::alist_impl_::alist_tag<double> >::Et, std::allocator<tifa_libs::graph_impl_::graph<tifa_libs::alist_impl_::alist_tag<double> >::Et> >&)::{lambda()#1}::operator()() const: ✓ Branch 5 taken 13674637 times. ✓ Branch 6 taken 96521497 times. tifa_libs::bellman_ford<tifa_libs::graph_impl_::graph<tifa_libs::alist_impl_::alist_tag<int> >, tifa_libs::fn_0::{lambda((auto:1&&)...)#1} const&>(tifa_libs::graph_impl_::graph<tifa_libs::alist_impl_::alist_tag<int> > const&, unsigned int, tifa_libs::fn_0::{lambda((auto:1&&)...)#1} const&, std::vector<tifa_libs::graph_impl_::graph<tifa_libs::alist_impl_::alist_tag<int> >::Et, std::allocator<tifa_libs::graph_impl_::graph<tifa_libs::alist_impl_::alist_tag<int> >::Et> >&)::{lambda()#1}::operator()() const: ✓ Branch 5 taken 10870 times. ✓ Branch 6 taken 26058 times. tifa_libs::bellman_ford<tifa_libs::graph_impl_::graph<tifa_libs::alist_impl_::alist_tag<long> >, tifa_libs::fn_0::{lambda((auto:1&&)...)#1} const&>(tifa_libs::graph_impl_::graph<tifa_libs::alist_impl_::alist_tag<long> > const&, unsigned int, tifa_libs::fn_0::{lambda((auto:1&&)...)#1} const&, std::vector<tifa_libs::graph_impl_::graph<tifa_libs::alist_impl_::alist_tag<long> >::Et, std::allocator<tifa_libs::graph_impl_::graph<tifa_libs::alist_impl_::alist_tag<long> >::Et> >&)::{lambda()#1}::operator()() const: ✓ Branch 5 taken 5540 times. ✓ Branch 6 taken 5776 times.	110244378	if (cb_relax(u, v), dis[v] = dis[u] + w; vis[v]) continue;
29	6/6 tifa_libs::bellman_ford<tifa_libs::graph_impl_::graph<tifa_libs::alist_impl_::alist_tag<double> >, tifa_libs::fn_0::{lambda((auto:1&&)...)#1} const&>(tifa_libs::graph_impl_::graph<tifa_libs::alist_impl_::alist_tag<double> > const&, unsigned int, tifa_libs::fn_0::{lambda((auto:1&&)...)#1} const&, std::vector<tifa_libs::graph_impl_::graph<tifa_libs::alist_impl_::alist_tag<double> >::Et, std::allocator<tifa_libs::graph_impl_::graph<tifa_libs::alist_impl_::alist_tag<double> >::Et> >&)::{lambda()#1}::operator()() const: ✓ Branch 1 taken 322 times. ✓ Branch 2 taken 96521175 times. tifa_libs::bellman_ford<tifa_libs::graph_impl_::graph<tifa_libs::alist_impl_::alist_tag<int> >, tifa_libs::fn_0::{lambda((auto:1&&)...)#1} const&>(tifa_libs::graph_impl_::graph<tifa_libs::alist_impl_::alist_tag<int> > const&, unsigned int, tifa_libs::fn_0::{lambda((auto:1&&)...)#1} const&, std::vector<tifa_libs::graph_impl_::graph<tifa_libs::alist_impl_::alist_tag<int> >::Et, std::allocator<tifa_libs::graph_impl_::graph<tifa_libs::alist_impl_::alist_tag<int> >::Et> >&)::{lambda()#1}::operator()() const: ✓ Branch 1 taken 9 times. ✓ Branch 2 taken 26049 times. tifa_libs::bellman_ford<tifa_libs::graph_impl_::graph<tifa_libs::alist_impl_::alist_tag<long> >, tifa_libs::fn_0::{lambda((auto:1&&)...)#1} const&>(tifa_libs::graph_impl_::graph<tifa_libs::alist_impl_::alist_tag<long> > const&, unsigned int, tifa_libs::fn_0::{lambda((auto:1&&)...)#1} const&, std::vector<tifa_libs::graph_impl_::graph<tifa_libs::alist_impl_::alist_tag<long> >::Et, std::allocator<tifa_libs::graph_impl_::graph<tifa_libs::alist_impl_::alist_tag<long> >::Et> >&)::{lambda()#1}::operator()() const: ✓ Branch 1 taken 7 times. ✓ Branch 2 taken 5769 times.	96553331	if (++dep[v] > n) return false;
30		96552993	vis[v] = true;
31	24/24 tifa_libs::bellman_ford<tifa_libs::graph_impl_::graph<tifa_libs::alist_impl_::alist_tag<double> >, tifa_libs::fn_0::{lambda((auto:1&&)...)#1} const&>(tifa_libs::graph_impl_::graph<tifa_libs::alist_impl_::alist_tag<double> > const&, unsigned int, tifa_libs::fn_0::{lambda((auto:1&&)...)#1} const&, std::vector<tifa_libs::graph_impl_::graph<tifa_libs::alist_impl_::alist_tag<double> >::Et, std::allocator<tifa_libs::graph_impl_::graph<tifa_libs::alist_impl_::alist_tag<double> >::Et> >&)::{lambda()#1}::operator()() const: ✓ Branch 1 taken 95918469 times. ✓ Branch 2 taken 602706 times. ✓ Branch 4 taken 92646052 times. ✓ Branch 5 taken 3272417 times. ✓ Branch 8 taken 92584794 times. ✓ Branch 9 taken 663964 times. ✓ Branch 12 taken 40148851 times. ✓ Branch 13 taken 53099907 times. tifa_libs::bellman_ford<tifa_libs::graph_impl_::graph<tifa_libs::alist_impl_::alist_tag<int> >, tifa_libs::fn_0::{lambda((auto:1&&)...)#1} const&>(tifa_libs::graph_impl_::graph<tifa_libs::alist_impl_::alist_tag<int> > const&, unsigned int, tifa_libs::fn_0::{lambda((auto:1&&)...)#1} const&, std::vector<tifa_libs::graph_impl_::graph<tifa_libs::alist_impl_::alist_tag<int> >::Et, std::allocator<tifa_libs::graph_impl_::graph<tifa_libs::alist_impl_::alist_tag<int> >::Et> >&)::{lambda()#1}::operator()() const: ✓ Branch 1 taken 21431 times. ✓ Branch 2 taken 4618 times. ✓ Branch 4 taken 10700 times. ✓ Branch 5 taken 10731 times. ✓ Branch 8 taken 15108 times. ✓ Branch 9 taken 210 times. ✓ Branch 12 taken 13067 times. ✓ Branch 13 taken 2251 times. tifa_libs::bellman_ford<tifa_libs::graph_impl_::graph<tifa_libs::alist_impl_::alist_tag<long> >, tifa_libs::fn_0::{lambda((auto:1&&)...)#1} const&>(tifa_libs::graph_impl_::graph<tifa_libs::alist_impl_::alist_tag<long> > const&, unsigned int, tifa_libs::fn_0::{lambda((auto:1&&)...)#1} const&, std::vector<tifa_libs::graph_impl_::graph<tifa_libs::alist_impl_::alist_tag<long> >::Et, std::allocator<tifa_libs::graph_impl_::graph<tifa_libs::alist_impl_::alist_tag<long> >::Et> >&)::{lambda()#1}::operator()() const: ✓ Branch 1 taken 3493 times. ✓ Branch 2 taken 2276 times. ✓ Branch 4 taken 2561 times. ✓ Branch 5 taken 932 times. ✓ Branch 8 taken 4768 times. ✓ Branch 9 taken 69 times. ✓ Branch 12 taken 1424 times. ✓ Branch 13 taken 3413 times.	96552993	(1 < dep[v] && dep[v] < sn) \|\| dis[v] < TPN G::Et(q.size() ? dis[q.front()] : 0) ? q.push_front(v) : q.push_back(v);
32		96552993	upd_q();
33			}
34			}
35		581349	return true;
36		581687	}
37			// cb_relax(now, to)
38			template <wgraph_c G, class F>
39		90	auto bellman_ford(G CR g, u32 s, F&& cb_relax, TPN G::Et INF = std::numeric_limits<TPN G::Et>::max() / 2 - 1) NE {
40		90	std::optional ret{vec<TPN G::Et>(g.vsize(), INF)};
41	4/4 auto tifa_libs::bellman_ford<tifa_libs::graph_impl_::graph<tifa_libs::alist_impl_::alist_tag<int> >, tifa_libs::fn_0::{lambda((auto:1&&)...)#1} const&>(tifa_libs::graph_impl_::graph<tifa_libs::alist_impl_::alist_tag<int> > const&, unsigned int, tifa_libs::fn_0::{lambda((auto:1&&)...)#1} const&, tifa_libs::graph_impl_::graph<tifa_libs::alist_impl_::alist_tag<int> >::Et): ✓ Branch 3 taken 9 times. ✓ Branch 4 taken 31 times. auto tifa_libs::bellman_ford<tifa_libs::graph_impl_::graph<tifa_libs::alist_impl_::alist_tag<long> >, tifa_libs::fn_0::{lambda((auto:1&&)...)#1} const&>(tifa_libs::graph_impl_::graph<tifa_libs::alist_impl_::alist_tag<long> > const&, unsigned int, tifa_libs::fn_0::{lambda((auto:1&&)...)#1} const&, tifa_libs::graph_impl_::graph<tifa_libs::alist_impl_::alist_tag<long> >::Et): ✓ Branch 3 taken 7 times. ✓ Branch 4 taken 43 times.	90	if (!bellman_ford(g, s, std::forward<F>(cb_relax), ret.value())) ret = std::nullopt;
42		90	return ret;
43			}
44
45			} // namespace tifa_libs
46