#690686 (C++17(gcc12)) No.1582 Vertexes vs Edges

提出ソース
結果

問題	No.1582 Vertexes vs Edges
コンテスト
ユーザー	jell
提出日時	2021-08-18 15:09:08
言語	C++17(gcc12) (gcc 12.3.0 + boost 1.87.0)
結果	WA
実行時間	-
コード長	13,492 bytes
コンパイル時間	4,199 ms
コンパイル使用メモリ	126,716 KB
最終ジャッジ日時	2025-01-23 22:54:05
ジャッジサーバーID （参考情報）	judge2 / judge1
このコードへのチャレンジ
（要ログイン）
ファイルパターン	結果
sample	WA * 2 RE * 1
other	WA * 27 RE * 9
権限があれば一括ダウンロードができます
ソースコード

raw source code
#line 1 "Library\\test\\library-checker\\shortest_path.test.cpp"
#define PROBLEM "https://judge.yosupo.jp/problem/shortest_path"

#include <iostream>

#line 2 "Library\\src\\graph\\digraph.h"

/**
 * @file digraph.h
 * @brief Digraph
 */

#include <list>
#include <numeric>
#include <queue>
#include <stack>
#include <vector>

#line 2 "Library\\src\\graph\\edge.h"

/**
 * @file edge.h
 * @brief Edge
 */

#line 2 "Library\\lib\\cxx17"

#ifndef _CXX17_CONSTEXPR
#if __cplusplus >= 201703L
#define _CXX17_CONSTEXPR constexpr
#else
#define _CXX17_CONSTEXPR
#endif
#endif

#ifndef _CXX17_STATIC_ASSERT
#if __cplusplus >= 201703L
#define _CXX17_STATIC_ASSERT static_assert
#else
#define _CXX17_STATIC_ASSERT assert
#endif
#endif

#include <iterator>

#if __cplusplus < 201703L

namespace std {

/**
 *  @brief  Return the size of a container.
 *  @param  __cont  Container.
 */
template <typename _Container>
constexpr auto size(const _Container& __cont) noexcept(noexcept(__cont.size()))
    -> decltype(__cont.size()) {
  return __cont.size();
}

/**
 *  @brief  Return the size of an array.
 */
template <typename _Tp, size_t _Nm>
constexpr size_t size(const _Tp (&)[_Nm]) noexcept {
  return _Nm;
}

struct monostate {};

template <class _Tp> class optional {
  _Tp __value;
  bool __has_value = false;

 public:
  constexpr operator bool() const noexcept { return __has_value; }
  constexpr bool has_value() const noexcept { return __has_value; }
  constexpr _Tp& value() noexcept { return __value; }
  constexpr const _Tp& value() const noexcept { return __value; }
};

}  // namespace std

#else

#include <optional>
#include <variant>

#endif
#line 9 "Library\\src\\graph\\edge.h"

namespace workspace {

struct null_attribute {};

template <class _Weight, class _Attr = null_attribute>
struct weighted_edge : _Attr {
  using attribute = _Attr;
  using value_type = _Weight;
  using node_type = size_t;

  node_type tail, head;
  value_type weight{};

  constexpr weighted_edge() = default;

  template <class... _Args>
  constexpr weighted_edge(node_type __u, node_type __v, value_type __c = 0,
                          _Args &&...__args) noexcept
      : _Attr(std::forward<_Args>(__args)...),
        tail(__u),
        head(__v),
        weight(__c) {}

  constexpr bool operator<(const weighted_edge &__e) const noexcept {
    return weight < __e.weight;
  }
  constexpr bool operator>(const weighted_edge &__e) const noexcept {
    return weight > __e.weight;
  }
};

template <class _Attr = null_attribute>
struct edge : weighted_edge<int, _Attr> {
  using base_type = weighted_edge<int, _Attr>;

  using typename base_type::node_type;
  using base_type::operator<;
  using base_type::operator>;

  constexpr edge() = default;

  template <class... _Args>
  constexpr edge(node_type __u, node_type __v, _Args &&...__args) noexcept
      : base_type(__u, __v, __u != __v, std::forward<_Args>(__args)...) {}
};

template <size_t _Nm, class _Attr>
constexpr std::tuple_element_t<_Nm, edge<_Attr>> &get(
    edge<_Attr> &__e) noexcept {
  if _CXX17_CONSTEXPR (_Nm > 1)
    return __e;
  else if _CXX17_CONSTEXPR (_Nm)
    return __e.head;
  else
    return __e.tail;
}

template <size_t _Nm, class _Attr>
constexpr const std::tuple_element_t<_Nm, edge<_Attr>> &get(
    const edge<_Attr> &__e) noexcept {
  if _CXX17_CONSTEXPR (_Nm > 1)
    return __e;
  else if _CXX17_CONSTEXPR (_Nm)
    return __e.head;
  else
    return __e.tail;
}

template <size_t _Nm, class _Attr>
constexpr std::tuple_element_t<_Nm, edge<_Attr>> &&get(
    edge<_Attr> &&__e) noexcept {
  return std::move(get<_Nm>(__e));
}

template <size_t _Nm, class _Weight, class _Attr>
constexpr const std::tuple_element_t<_Nm, weighted_edge<_Weight, _Attr>> &get(
    const weighted_edge<_Weight, _Attr> &__e) noexcept {
  if _CXX17_CONSTEXPR (_Nm > 2)
    return __e;
  else if _CXX17_CONSTEXPR (_Nm > 1)
    return __e.weight;
  else if _CXX17_CONSTEXPR (_Nm)
    return __e.head;
  else
    return __e.tail;
}

template <size_t _Nm, class _Weight, class _Attr>
constexpr std::tuple_element_t<_Nm, weighted_edge<_Weight, _Attr>> &get(
    weighted_edge<_Weight, _Attr> &__e) noexcept {
  if _CXX17_CONSTEXPR (_Nm > 2)
    return __e;
  else if _CXX17_CONSTEXPR (_Nm > 1)
    return __e.weight;
  else if _CXX17_CONSTEXPR (_Nm)
    return __e.head;
  else
    return __e.tail;
}

template <size_t _Nm, class _Weight, class _Attr>
constexpr std::tuple_element_t<_Nm, weighted_edge<_Weight, _Attr>> &&get(
    weighted_edge<_Weight, _Attr> &&__e) noexcept {
  return std::move(get<_Nm>(__e));
}

}  // namespace workspace

namespace std {

template <class _Attr>
struct tuple_size<workspace::edge<_Attr>> : integral_constant<size_t, 3> {};

template <>
struct tuple_size<workspace::edge<>> : integral_constant<size_t, 2> {};

template <class _Weight, class _Attr>
struct tuple_size<workspace::weighted_edge<_Weight, _Attr>>
    : integral_constant<size_t, 4> {};

template <class _Weight>
struct tuple_size<workspace::weighted_edge<_Weight>>
    : integral_constant<size_t, 3> {};

template <size_t _Nm, class _Attr>
struct tuple_element<_Nm, workspace::edge<_Attr>> {
  using type = std::conditional_t<(_Nm < 2), size_t, _Attr>;
};

template <size_t _Nm, class _Weight, class _Attr>
struct tuple_element<_Nm, workspace::weighted_edge<_Weight, _Attr>> {
  using type = std::conditional_t<(_Nm < 2), size_t,
                                  std::conditional_t<_Nm == 2, _Weight, _Attr>>;
};

}  // namespace std
#line 15 "Library\\src\\graph\\digraph.h"

namespace workspace {

template <class _Attr = null_attribute, class _List = std::vector<edge<_Attr>>>
class digraph : std::vector<_List> {
 public:
  using container_type = std::vector<_List>;
  using size_type = typename container_type::size_type;

  using node_type = size_type;
  using edge_type = typename _List::value_type;

  using container_type::operator[];

  using container_type::begin;
  using container_type::end;

  using container_type::empty;
  using container_type::size;

  digraph(size_type __n = 0) : container_type(__n) {}

  /**
   * @brief Add some nodes to the graph.
   * @param __n Number of nodes added
   * @return List of indices of the nodes.
   */
  auto add_nodes(size_type __n) noexcept {
    std::vector<node_type> __ret(__n);
    std::iota(__ret.begin(), __ret.end(), size());
    container_type::resize(__n + size());
    return __ret;
  }

  node_type add_node() noexcept { return add_nodes(1).front(); }

  template <class... _Args>
  decltype(auto) add_edge(node_type __u, node_type __v,
                          _Args &&...__args) noexcept {
    return operator[](__u).emplace_back(__u, __v,
                                        std::forward<_Args>(__args)...);
  }

  decltype(auto) add_edge(const edge_type &__e) noexcept {
    return operator[](__e.tail).emplace_back(__e);
  }

  /**
   * @brief Single-source DFS.
   * @return Edges of DFS-tree in the search order.
   */
  decltype(auto) dfs(node_type __r) noexcept {
    node_type __a[]{__r};
    return dfs(__a, __a + 1);
  }

  /**
   * @brief Multi-source DFS.
   * @return Edges of DFS-tree in the search order.
   */
  template <class _Iterator>
  decltype(auto) dfs(_Iterator __first, _Iterator __last) noexcept {
    return search<false, std::stack<edge_type>>(__first, __last);
  }

  /**
   * @brief Single-source BFS.
   * @return Edges of BFS-tree in the search order.
   */
  decltype(auto) bfs(node_type __r) noexcept {
    node_type __a[]{__r};
    return bfs(__a, __a + 1);
  }

  /**
   * @brief Multi-source BFS.
   * @return Edges of BFS-tree in the search order.
   */
  template <class _Iterator>
  decltype(auto) bfs(_Iterator __first, _Iterator __last) noexcept {
    return search<false, std::queue<edge_type>>(__first, __last);
  }

  /**
   * @brief Prim's algorithm.
   * @param __r Starting vertex. Defalut: 0.
   * @return Edges of a minimum spanning tree (of the connected component).
   */
  decltype(auto) prim(node_type __r = 0) noexcept {
    node_type __a[]{__r};
    return prim(__a, __a + 1);
  }

  /**
   * @brief Prim's algorithm.
   * @param __r Starting vertices. Defalut: 0.
   * @return Edges of a minimum spanning tree (of the connected component).
   */
  template <class _Iterator>
  decltype(auto) prim(_Iterator __first, _Iterator __last) noexcept {
    return search<false, std::priority_queue<edge_type, std::vector<edge_type>,
                                             std::greater<>>>(__first, __last);
  }

  /**
   * @brief Single-source Dijkstra's algorithm.
   * @return Edges of shortest path tree in the search order.
   */
  decltype(auto) dijkstra(node_type __r) noexcept {
    node_type __a[]{__r};
    return dijkstra(__a, __a + 1);
  }

  /**
   * @brief Multi-source Dijkstra's algorithm.
   * @return Edges of shortest path tree in the search order.
   */
  template <class _Iterator>
  decltype(auto) dijkstra(_Iterator __first, _Iterator __last) noexcept {
    return get_distance<std::priority_queue<edge_type, std::vector<edge_type>,
                                            std::greater<edge_type>>>(__first,
                                                                      __last);
  }

  /**
   * @brief Single-source Bellman-Ford algorithm.
   * @return Edges of shortest path tree in the search order.
   */
  decltype(auto) bellman_ford() noexcept {
    std::vector<node_type> __a(size());
    return bellman_ford(__a.begin(), __a.end());
  }

  /**
   * @brief Multi-source Bellman-Ford algorithm.
   * @return Edges of shortest path tree in the search order.
   */
  decltype(auto) bellman_ford(node_type __r) noexcept {
    node_type __a[]{__r};
    return bellman_ford(__a, __a + 1);
  }

  template <class _Iterator>
  decltype(auto) bellman_ford(_Iterator __first, _Iterator __last) noexcept {
    return get_distance<std::queue<edge_type>>(__first, __last);
  }

  decltype(auto) warshall_floyd(node_type __r) noexcept;

 protected:
  /**
   * @brief Search from given vertex set.
   * @tparam _Add_weight Need distance or not.
   * @tparam _Container Queue.
   */
  template <bool _Add_weight, class _Container, class _Iterator>
  auto search(_Iterator __first, _Iterator __last) const noexcept {
    static std::vector<int_fast8_t> __visited;
    __visited.resize(size());

    std::vector<edge_type> __tree;
    queue_wrapper<_Container> __queue;

    for (auto __s = __first; __s != __last; __visited[*__s++] = true)
      for (auto &&__e : operator[](*__s)) __queue.emplace(__e);

    while (!__queue.empty()) {
      auto __p = __queue.pop();

      if (__visited[__p.head]) continue;
      __visited[__p.head] = true;

      for (auto __e : operator[](__p.head)) {
        if _CXX17_CONSTEXPR (_Add_weight) __e.weight += __p.weight;
        __queue.emplace(std::move(__e));
      }

      __tree.emplace_back(std::move(__p));
    }

    for (auto __s = __first; __s != __last; __visited[*__s++] = false) continue;
    for (auto &&__e : __tree) __visited[__e.head] = false;

    return __tree;
  }

  template <class _Container, class _Iterator>
  auto get_distance(_Iterator __first, _Iterator __last) const noexcept {
    using iterator = typename std::list<edge_type>::iterator;
    struct info : iterator {
      bool empty = true;
    };
    static std::vector<info> __prev;
    __prev.resize(size());

    std::list<edge_type> __tree;
    queue_wrapper<_Container> __queue;

    for (; __first != __last; ++__first) __queue.emplace(*__first, *__first);

    while (!__queue.empty()) {
      auto &&__p = __queue.pop();
      auto &&__l = __prev[__p.head];

      if (!__l.empty && !(__p.weight < __l->weight)) continue;

      if (__l.empty)
        __l.empty = false;
      else
        __tree.erase((iterator &)__l);

      for (auto __e : operator[](__p.head))
        __e.weight += __p.weight, __queue.emplace(std::move(__e));

      (iterator &)__l = __tree.emplace(__tree.end(), __p);
    }

    for (auto &&__e : __tree) __prev[__e.head].empty = true;
    __tree.remove_if([](auto &&__e) { return __e.tail == __e.head; });

    return __tree;
  }

  template <class _Base, class = void> struct queue_wrapper : _Base {
    auto pop() noexcept {
      auto __tmp = std::move(_Base::front());
      _Base::pop();
      return __tmp;
    }
  };

  template <class _Base>
  struct queue_wrapper<_Base,
                       std::__void_t<decltype(std::declval<_Base>().top())>>
      : _Base {
    auto pop() noexcept {
      auto __tmp = std::move(_Base::top());
      _Base::pop();
      return __tmp;
    }
  };
};

template <class _Weight, class _Attr = null_attribute,
          class _List = std::vector<weighted_edge<_Weight, _Attr>>>
class weighted_digraph : public digraph<_Attr, _List> {
  using digraph<_Attr, _List>::digraph;
};

}  // namespace workspace
#line 6 "Library\\test\\library-checker\\shortest_path.test.cpp"

int main() {
  int n, m, s, t, a, b, c;
  std::cin >> n >> m >> s >> t;

  workspace::weighted_digraph<long long> g(n);
  while (m--) {
    std::cin >> a >> b >> c;
    g.add_edge(a, b, c);
  }

  auto edges = g.dijkstra(s);
  std::vector<decltype(g)::edge_type> path;

  for (auto i = edges.rbegin(); i != edges.rend(); ++i)
    if (i->head == t) t = i->tail, path.emplace_back(*i);

  if (s != t) {
    std::cout << "-1\n";
    return 0;
  }

  std::cout << path.front().weight << " " << path.size() << "\n";

  for (auto i = path.rbegin(); i != path.rend(); ++i)
    std::cout << i->tail << " " << i->head << "\n";
}
yukicoder

結果

ソースコード
