tests/persistent_stack.test.cpp

View this file on GitHub
Last update: 2025-01-26 15:10:23+09:00
Problem: https://judge.yosupo.jp/problem/shortest_path

Depends on

Code

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

#include <iostream>
#include <vector>
#include <utility>
#include <limits>
#include <queue>
#include <algorithm>
#include <iterator>
#include "tools/persistent_stack.hpp"
#include "tools/greater_by_second.hpp"
#include "tools/chmin.hpp"

using ll = long long;

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

  ll N, M, s, t;
  std::cin >> N >> M >> s >> t;
  std::vector<std::vector<std::pair<ll, ll>>> graph(N);
  for (ll i = 0; i < M; ++i) {
    ll a, b, c;
    std::cin >> a >> b >> c;
    graph[a].emplace_back(b, c);
  }

  std::vector<ll> dist(N, std::numeric_limits<ll>::max());
  dist[s] = 0;

  tools::persistent_stack<ll>::buffer buffer;
  std::vector<tools::persistent_stack<ll>> path(N, tools::persistent_stack<ll>(buffer));
  path[s] = path[s].push(s);

  std::priority_queue<std::pair<ll, ll>, std::vector<std::pair<ll, ll>>, 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& [next, w] : graph[here]) {
      if (tools::chmin(dist[next], dist[here] + w)) {
        path[next] = path[here].push(next);
        pq.emplace(next, dist[next]);
      }
    }
  }

  if (dist[t] == std::numeric_limits<ll>::max()) {
    std::cout << -1 << '\n';
    return 0;
  }

  std::cout << dist[t] << ' ' << path[t].size() - 1 << '\n';
  std::vector<ll> answers;
  for (auto stack = path[t]; !stack.empty(); stack = stack.pop()) {
    answers.push_back(stack.top());
  }
  std::reverse(answers.begin(), answers.end());
  for (ll i = 0; i + 1 < std::ssize(answers); ++i) {
    std::cout << answers[i] << ' ' << answers[i + 1] << '\n';
  }

  return 0;
}

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

#include <iostream>
#include <vector>
#include <utility>
#include <limits>
#include <queue>
#include <algorithm>
#include <iterator>
#line 1 "tools/persistent_stack.hpp"



#include <cstddef>
#line 7 "tools/persistent_stack.hpp"
#include <cassert>
#include <type_traits>

namespace tools {
  template <typename T>
  class persistent_stack {
  private:
    struct node {
      ::std::size_t parent;
      ::std::size_t depth;
      T value;
    };

  public:
    class buffer {
    private:
      ::std::vector<::tools::persistent_stack<T>::node> m_nodes;

    public:
      buffer() = default;
      buffer(const ::tools::persistent_stack<T>::buffer&) = default;
      buffer(::tools::persistent_stack<T>::buffer&&) = default;
      ~buffer() = default;
      ::tools::persistent_stack<T>::buffer& operator=(const ::tools::persistent_stack<T>::buffer&) = default;
      ::tools::persistent_stack<T>::buffer& operator=(::tools::persistent_stack<T>::buffer&&) = default;

      friend ::tools::persistent_stack<T>;
    };

  private:
    static const ::std::size_t EMPTY = ::std::numeric_limits<::std::size_t>::max();
    ::tools::persistent_stack<T>::buffer *m_buffer;
    ::std::size_t m_top;

    persistent_stack(::tools::persistent_stack<T>::buffer& buffer, const ::std::size_t top) : m_buffer(&buffer), m_top(top) {
    }

  public:
    persistent_stack() = default;
    persistent_stack(const ::tools::persistent_stack<T>&) = default;
    persistent_stack(::tools::persistent_stack<T>&&) = default;
    ~persistent_stack() = default;
    ::tools::persistent_stack<T>& operator=(const ::tools::persistent_stack<T>&) = default;
    ::tools::persistent_stack<T>& operator=(::tools::persistent_stack<T>&&) = default;

    explicit persistent_stack(::tools::persistent_stack<T>::buffer& buffer) : m_buffer(&buffer), m_top(EMPTY) {
    }

    bool empty() const {
      return this->m_top == EMPTY;
    }

    ::std::size_t size() const {
      return this->empty() ? 0 : this->m_buffer->m_nodes[this->m_top].depth + 1;
    }

    T top() const {
      assert(!this->empty());
      return this->m_buffer->m_nodes[this->m_top].value;
    }

    ::tools::persistent_stack<T> push(const T& x) const {
      this->m_buffer->m_nodes.emplace_back();
      this->m_buffer->m_nodes.back().parent = this->m_top;
      this->m_buffer->m_nodes.back().depth = this->empty() ? 0 : this->m_buffer->m_nodes[this->m_top].depth + 1;
      this->m_buffer->m_nodes.back().value = x;
      return ::tools::persistent_stack<T>(*this->m_buffer, this->m_buffer->m_nodes.size() - 1);
    }

    ::tools::persistent_stack<T> pop() const {
      assert(!this->empty());
      return ::tools::persistent_stack<T>(*this->m_buffer, this->m_buffer->m_nodes[this->m_top].parent);
    }

    template <typename... Args>
    ::tools::persistent_stack<T> emplace(Args&&... args) const {
      return this->push(T(::std::forward<Args>(args)...));
    }
  };
}


#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/chmin.hpp"



#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 13 "tests/persistent_stack.test.cpp"

using ll = long long;

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

  ll N, M, s, t;
  std::cin >> N >> M >> s >> t;
  std::vector<std::vector<std::pair<ll, ll>>> graph(N);
  for (ll i = 0; i < M; ++i) {
    ll a, b, c;
    std::cin >> a >> b >> c;
    graph[a].emplace_back(b, c);
  }

  std::vector<ll> dist(N, std::numeric_limits<ll>::max());
  dist[s] = 0;

  tools::persistent_stack<ll>::buffer buffer;
  std::vector<tools::persistent_stack<ll>> path(N, tools::persistent_stack<ll>(buffer));
  path[s] = path[s].push(s);

  std::priority_queue<std::pair<ll, ll>, std::vector<std::pair<ll, ll>>, 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& [next, w] : graph[here]) {
      if (tools::chmin(dist[next], dist[here] + w)) {
        path[next] = path[here].push(next);
        pq.emplace(next, dist[next]);
      }
    }
  }

  if (dist[t] == std::numeric_limits<ll>::max()) {
    std::cout << -1 << '\n';
    return 0;
  }

  std::cout << dist[t] << ' ' << path[t].size() - 1 << '\n';
  std::vector<ll> answers;
  for (auto stack = path[t]; !stack.empty(); stack = stack.pop()) {
    answers.push_back(stack.top());
  }
  std::reverse(answers.begin(), answers.end());
  for (ll i = 0; i + 1 < std::ssize(answers); ++i) {
    std::cout << answers[i] << ' ' << answers[i + 1] << '\n';
  }

  return 0;
}

Test cases

Env	Name	Status	Elapsed	Memory
g++	almost_line_00	AC	183 ms	43 MB
g++	almost_line_01	AC	171 ms	42 MB
g++	almost_line_02	AC	168 ms	43 MB
g++	example_00	AC	5 ms	4 MB
g++	example_01	AC	4 ms	4 MB
g++	grid_random_00	AC	132 ms	26 MB
g++	grid_swirl_00	AC	160 ms	30 MB
g++	line_00	AC	265 ms	62 MB
g++	max_dense_long_00	AC	79 ms	14 MB
g++	max_dense_random_00	AC	80 ms	14 MB
g++	max_dense_random_01	AC	79 ms	14 MB
g++	max_dense_zero_00	AC	76 ms	14 MB
g++	max_sparse_random_00	AC	126 ms	28 MB
g++	max_sparse_random_01	AC	174 ms	37 MB
g++	max_sparse_random_02	AC	175 ms	36 MB
g++	max_star_00	AC	172 ms	62 MB
g++	max_star_01	AC	250 ms	61 MB
g++	small_00	AC	5 ms	4 MB
g++	small_01	AC	4 ms	4 MB
g++	small_02	AC	4 ms	4 MB
g++	small_03	AC	4 ms	4 MB
g++	small_04	AC	4 ms	4 MB
g++	sparse_random_00	AC	101 ms	32 MB
g++	sparse_random_01	AC	104 ms	36 MB
g++	sparse_random_02	AC	109 ms	20 MB
g++	spfa_killer_00	AC	218 ms	54 MB
g++	wrong_dijkstra_handmade_00	AC	5 ms	4 MB
g++	wrong_dijkstra_killer_00	AC	172 ms	45 MB
g++	wrong_dijkstra_killer_01	AC	267 ms	51 MB