tests/dijkstra/directed.test.cpp

• View this file on GitHub
• Last update: 2025-02-23 20:12:17+09:00
• Problem: https://judge.yosupo.jp/problem/shortest_path

Depends on

• chmin function (tools/chmin.hpp)
• Dijkstra's algorithm (tools/dijkstra.hpp)
• std::greater by second (tools/greater_by_second.hpp)
• Shortest path tree (tools/shortest_path_tree.hpp)

Code

// competitive-verifier: PROBLEM https://judge.yosupo.jp/problem/shortest_path

#include <iostream>
#include <limits>
#include <ranges>
#include <vector>
#include "tools/dijkstra.hpp"

using ll = long long;

int main() {
  std::cin.tie(nullptr);
  std::ios_base::sync_with_stdio(false);

  int N, M, s, t;
  std::cin >> N >> M >> s >> t;

  tools::dijkstra<true, ll> graph(N);
  for (int i = 0; i < M; ++i) {
    int a, b, c;
    std::cin >> a >> b >> c;
    graph.add_edge(a, b, c);
  }

  const auto qr = graph.query<true>(s);
  if (qr.dist(t) == std::numeric_limits<ll>::max()) {
    std::cout << -1 << '\n';
  } else {
    const auto path = qr.edge_id_path(t);
    std::cout << qr.dist(t) << ' ' << path.size() << '\n';
    for (const auto& edge : path | std::views::transform([&](const auto k) { return graph.get_edge(k); })) {
      std::cout << edge.from << ' ' << edge.to << '\n';
    }
  }

  return 0;
}

#line 1 "tests/dijkstra/directed.test.cpp"
// competitive-verifier: PROBLEM https://judge.yosupo.jp/problem/shortest_path

#include <iostream>
#include <limits>
#include <ranges>
#include <vector>
#line 1 "tools/dijkstra.hpp"



#include <algorithm>
#include <cassert>
#include <iterator>
#line 8 "tools/dijkstra.hpp"
#include <queue>
#include <tuple>
#include <utility>
#line 1 "tools/chmin.hpp"



#include <type_traits>
#line 6 "tools/chmin.hpp"

namespace tools {

  template <typename M, typename N>
  bool chmin(M& lhs, const N& rhs) {
    bool updated;
    if constexpr (::std::is_integral_v<M> && ::std::is_integral_v<N>) {
      updated = ::std::cmp_less(rhs, lhs);
    } else {
      updated = rhs < lhs;
    }
    if (updated) lhs = rhs;
    return updated;
  }
}


#line 1 "tools/greater_by_second.hpp"



#line 5 "tools/greater_by_second.hpp"

namespace tools {

  class greater_by_second {
  public:
    template <class T1, class T2>
    bool operator()(const ::std::pair<T1, T2>& x, const ::std::pair<T1, T2>& y) const {
      return x.second > y.second;
    }
  };
}


#line 1 "tools/shortest_path_tree.hpp"



#line 10 "tools/shortest_path_tree.hpp"

namespace tools {
  template <typename Cost, typename F>
  class shortest_path_tree {
    ::std::vector<Cost> m_dist;
    ::std::vector<int> m_from;
    F m_get_vertex;

  public:
    shortest_path_tree() = default;
    template <::std::ranges::range R1, ::std::ranges::range R2>
    shortest_path_tree(R1&& d, R2&& p, const F& f) : m_get_vertex(f) {
      ::std::ranges::copy(d, ::std::back_inserter(this->m_dist));
      ::std::ranges::copy(p, ::std::back_inserter(this->m_from));
      assert(this->m_dist.size() == this->m_from.size());
      assert(::std::ranges::all_of(this->m_from, [](const auto p_i) { return p_i >= -1; }));
    }

    int size() const {
      return this->m_dist.size();
    }
    const ::std::vector<Cost>& dist() const & {
      return this->m_dist;
    }
    ::std::vector<Cost> dist() && {
      return ::std::move(this->m_dist);
    }
    Cost dist(const int v) const {
      assert(0 <= v && v < this->size());
      return this->m_dist[v];
    }
    int from_vertex(const int v) const {
      assert(0 <= v && v < this->size());
      return this->m_from[v] >= 0 ? this->m_get_vertex(this->m_from[v], v) : -1;
    }
    int from_edge_id(const int v) const {
      assert(0 <= v && v < this->size());
      return this->m_from[v];
    }
    ::std::vector<int> vertex_path(const int v) const {
      assert(0 <= v && v < this->size());
      ::std::vector<int> path;
      for (int u = v; u >= 0; u = this->from_vertex(u)) {
        path.push_back(u);
      }
      ::std::ranges::reverse(path);
      return path;
    }
    ::std::vector<int> edge_id_path(const int v) const {
      assert(0 <= v && v < this->size());
      ::std::vector<int> path;
      for (int u = v; this->m_from[u] >= 0; u = this->from_vertex(u)) {
        path.push_back(this->m_from[u]);
      }
      ::std::ranges::reverse(path);
      return path;
    }
  };

  template <::std::ranges::range R1, ::std::ranges::range R2, typename F>
  shortest_path_tree(R1&&, R2&&, const F&) -> shortest_path_tree<::std::ranges::range_value_t<R1>, F>;
}


#line 15 "tools/dijkstra.hpp"

namespace tools {

  template <bool Directed, typename T>
  class dijkstra {
  public:
    struct edge {
      int from;
      int to;
      T cost;
    };

  private:
    ::std::vector<edge> m_edges;
    ::std::vector<::std::vector<int>> m_graph;

  public:
    dijkstra() = default;
    explicit dijkstra(const int n) : m_graph(n) {
    }

    int size() const {
      return this->m_graph.size();
    }

    int add_edge(int u, int v, const T w) {
      assert(0 <= u && u < this->size());
      assert(0 <= v && v < this->size());
      assert(w >= 0);
      if constexpr (!Directed) {
        ::std::tie(u, v) = ::std::minmax({u, v});
      }
      this->m_edges.push_back({u, v, w});
      this->m_graph[u].push_back(this->m_edges.size() - 1);
      if constexpr (!Directed) {
        this->m_graph[v].push_back(this->m_edges.size() - 1);
      }
      return this->m_edges.size() - 1;
    }

    const edge& get_edge(const int k) const & {
      assert(0 <= k && k < ::std::ssize(this->m_edges));
      return this->m_edges[k];
    }
    edge get_edge(const int k) && {
      assert(0 <= k && k < ::std::ssize(this->m_edges));
      return ::std::move(this->m_edges[k]);
    }

    const ::std::vector<edge>& edges() const & {
      return this->m_edges;
    }
    ::std::vector<edge> edges() && {
      return ::std::move(this->m_edges);
    }

    template <bool Restore = false>
    auto query(const int s) const {
      assert(0 <= s && s < this->size());

      ::std::vector<T> dist(this->size(), ::std::numeric_limits<T>::max());
      dist[s] = 0;
      ::std::vector<int> prev(Restore ? this->size() : 0, -1);

      ::std::priority_queue<::std::pair<int, T>, ::std::vector<::std::pair<int, T>>, ::tools::greater_by_second> pq;
      pq.emplace(s, 0);

      while (!pq.empty()) {
        const auto [here, d] = pq.top();
        pq.pop();
        if (dist[here] < d) continue;
        for (const auto edge_id : this->m_graph[here]) {
          const auto& edge = this->m_edges[edge_id];
          const auto next = edge.to ^ (Directed ? 0 : edge.from ^ here);
          if (::tools::chmin(dist[next], dist[here] + edge.cost)) {
            if constexpr (Restore) {
              prev[next] = edge_id;
            }
            pq.emplace(next, dist[next]);
          }
        }
      }

      if constexpr (Restore) {
        return ::tools::shortest_path_tree(dist, prev, [&](const auto e, const auto v) {
          return this->m_edges[e].from ^ (Directed ? 0 : this->m_edges[e].to ^ v);
        });
      } else {
        return dist;
      }
    }
  };
}


#line 8 "tests/dijkstra/directed.test.cpp"

using ll = long long;

int main() {
  std::cin.tie(nullptr);
  std::ios_base::sync_with_stdio(false);

  int N, M, s, t;
  std::cin >> N >> M >> s >> t;

  tools::dijkstra<true, ll> graph(N);
  for (int i = 0; i < M; ++i) {
    int a, b, c;
    std::cin >> a >> b >> c;
    graph.add_edge(a, b, c);
  }

  const auto qr = graph.query<true>(s);
  if (qr.dist(t) == std::numeric_limits<ll>::max()) {
    std::cout << -1 << '\n';
  } else {
    const auto path = qr.edge_id_path(t);
    std::cout << qr.dist(t) << ' ' << path.size() << '\n';
    for (const auto& edge : path | std::views::transform([&](const auto k) { return graph.get_edge(k); })) {
      std::cout << edge.from << ' ' << edge.to << '\n';
    }
  }

  return 0;
}

Test cases

Env	Name	Status	Elapsed	Memory
g++	almost_line_00	AC	184 ms	32 MB
g++	almost_line_01	AC	167 ms	32 MB
g++	almost_line_02	AC	182 ms	32 MB
g++	example_00	AC	7 ms	4 MB
g++	example_01	AC	6 ms	4 MB
g++	grid_random_00	AC	152 ms	21 MB
g++	grid_swirl_00	AC	185 ms	24 MB
g++	line_00	AC	354 ms	53 MB
g++	max_dense_long_00	AC	102 ms	14 MB
g++	max_dense_random_00	AC	105 ms	14 MB
g++	max_dense_random_01	AC	102 ms	14 MB
g++	max_dense_zero_00	AC	97 ms	14 MB
g++	max_sparse_random_00	AC	149 ms	31 MB
g++	max_sparse_random_01	AC	196 ms	32 MB
g++	max_sparse_random_02	AC	207 ms	32 MB
g++	max_star_00	AC	205 ms	46 MB
g++	max_star_01	AC	275 ms	52 MB
g++	small_00	AC	7 ms	4 MB
g++	small_01	AC	6 ms	4 MB
g++	small_02	AC	6 ms	4 MB
g++	small_03	AC	6 ms	4 MB
g++	small_04	AC	7 ms	4 MB
g++	sparse_random_00	AC	125 ms	39 MB
g++	sparse_random_01	AC	140 ms	43 MB
g++	sparse_random_02	AC	124 ms	18 MB
g++	spfa_killer_00	AC	212 ms	40 MB
g++	wrong_dijkstra_handmade_00	AC	8 ms	4 MB
g++	wrong_dijkstra_killer_00	AC	195 ms	39 MB
g++	wrong_dijkstra_killer_01	AC	241 ms	43 MB

Back to top page