C++ Library for Competitive Programming
View the Project on GitHub emthrm/cp-library
/* * @title グラフ/内周 * * verification-helper: PROBLEM https://yukicoder.me/problems/no/1320 */ #include <iostream> #include <limits> #include <vector> #include "emthrm/graph/edge.hpp" #include "emthrm/graph/girth_in_directed_graph.hpp" #include "emthrm/graph/girth_in_undirected_graph.hpp" int main() { constexpr long long LINF = std::numeric_limits<long long>::max(); int t, n, m; std::cin >> t >> n >> m; if (t == 0) { std::vector<emthrm::Edge<long long>> edges; while (m--) { int u, v, w; std::cin >> u >> v >> w; --u; --v; edges.emplace_back(u, v, w); } const long long ans = emthrm::girth_in_undirected_graph(n, edges, LINF); std::cout << (ans == LINF ? -1 : ans) << '\n'; } else if (t == 1) { std::vector<std::vector<emthrm::Edge<long long>>> graph(n); while (m--) { int u, v, w; std::cin >> u >> v >> w; --u; --v; graph[u].emplace_back(u, v, w); } const long long ans = emthrm::girth_in_directed_graph(graph, LINF); std::cout << (ans == LINF ? -1 : ans) << '\n'; } return 0; }
#line 1 "test/graph/girth.test.cpp" /* * @title グラフ/内周 * * verification-helper: PROBLEM https://yukicoder.me/problems/no/1320 */ #include <iostream> #include <limits> #include <vector> #line 1 "include/emthrm/graph/edge.hpp" /** * @title 辺 */ #ifndef EMTHRM_GRAPH_EDGE_HPP_ #define EMTHRM_GRAPH_EDGE_HPP_ #include <compare> namespace emthrm { template <typename CostType> struct Edge { CostType cost; int src, dst; explicit Edge(const int src, const int dst, const CostType cost = 0) : cost(cost), src(src), dst(dst) {} auto operator<=>(const Edge& x) const = default; }; } // namespace emthrm #endif // EMTHRM_GRAPH_EDGE_HPP_ #line 1 "include/emthrm/graph/girth_in_directed_graph.hpp" #include <algorithm> #include <functional> #line 7 "include/emthrm/graph/girth_in_directed_graph.hpp" #include <queue> #include <utility> #line 10 "include/emthrm/graph/girth_in_directed_graph.hpp" #line 1 "include/emthrm/graph/edge.hpp" /** * @title 辺 */ #ifndef EMTHRM_GRAPH_EDGE_HPP_ #define EMTHRM_GRAPH_EDGE_HPP_ #include <compare> namespace emthrm { template <typename CostType> struct Edge { CostType cost; int src, dst; explicit Edge(const int src, const int dst, const CostType cost = 0) : cost(cost), src(src), dst(dst) {} auto operator<=>(const Edge& x) const = default; }; } // namespace emthrm #endif // EMTHRM_GRAPH_EDGE_HPP_ #line 12 "include/emthrm/graph/girth_in_directed_graph.hpp" namespace emthrm { template <typename CostType> CostType girth_in_directed_graph( const std::vector<std::vector<Edge<CostType>>>& graph, const CostType inf = std::numeric_limits<CostType>::max()) { const int n = graph.size(); CostType res = inf; std::vector<CostType> dist(n); std::priority_queue<std::pair<CostType, int>, std::vector<std::pair<CostType, int>>, std::greater<std::pair<CostType, int>>> que; for (int root = 0; root < n; ++root) { std::fill(dist.begin(), dist.end(), inf); dist[root] = 0; que.emplace(dist[root], root); while (!que.empty()) { const auto [d, ver] = que.top(); que.pop(); if (d > dist[ver]) continue; for (const Edge<CostType>& e : graph[ver]) { const CostType nxt = dist[ver] + e.cost; if (nxt < dist[e.dst]) { dist[e.dst] = nxt; que.emplace(nxt, e.dst); } else if (e.dst == root) { res = std::min(res, nxt); } } } } return res; } } // namespace emthrm #line 1 "include/emthrm/graph/girth_in_undirected_graph.hpp" #line 10 "include/emthrm/graph/girth_in_undirected_graph.hpp" #line 1 "include/emthrm/graph/edge.hpp" /** * @title 辺 */ #ifndef EMTHRM_GRAPH_EDGE_HPP_ #define EMTHRM_GRAPH_EDGE_HPP_ #include <compare> namespace emthrm { template <typename CostType> struct Edge { CostType cost; int src, dst; explicit Edge(const int src, const int dst, const CostType cost = 0) : cost(cost), src(src), dst(dst) {} auto operator<=>(const Edge& x) const = default; }; } // namespace emthrm #endif // EMTHRM_GRAPH_EDGE_HPP_ #line 12 "include/emthrm/graph/girth_in_undirected_graph.hpp" namespace emthrm { template <typename CostType> CostType girth_in_undirected_graph( const int n, const std::vector<Edge<CostType>>& edges, const CostType inf = std::numeric_limits<CostType>::max()) { const int m = edges.size(); std::vector<std::vector<int>> graph(n); for (int i = 0; i < m; ++i) { graph[edges[i].src].emplace_back(i); graph[edges[i].dst].emplace_back(i); } std::vector<bool> is_used(m, false); std::vector<int> label(n), prev(n); std::vector<CostType> dist(n); std::priority_queue<std::pair<CostType, int>, std::vector<std::pair<CostType, int>>, std::greater<std::pair<CostType, int>>> que; CostType res = inf; for (int root = 0; root < n; ++root) { std::fill(is_used.begin(), is_used.end(), false); std::fill(label.begin(), label.end(), -2); label[root] = -1; std::fill(prev.begin(), prev.end(), -1); std::fill(dist.begin(), dist.end(), inf); dist[root] = 0; que.emplace(0, root); while (!que.empty()) { const auto [d, ver] = que.top(); que.pop(); if (d > dist[ver]) continue; for (const int id : graph[ver]) { const int dst = (edges[id].src == ver ? edges[id].dst : edges[id].src); const CostType nxt = dist[ver] + edges[id].cost; if (nxt < dist[dst]) { dist[dst] = nxt; label[dst] = (label[ver] == -1 ? dst : label[ver]); if (prev[dst] != -1) is_used[dst] = true; is_used[id] = true; que.emplace(nxt, dst); } } } for (int i = 0; i < m; ++i) { const int src = edges[i].src, dst = edges[i].dst; if (!is_used[i] && label[src] != -2 && label[dst] != -2) { if (label[src] != label[dst]) { res = std::min(res, dist[src] + dist[dst] + edges[i].cost); } else if (label[src] == -1) { res = std::min(res, edges[i].cost); } } } } return res; } } // namespace emthrm #line 14 "test/graph/girth.test.cpp" int main() { constexpr long long LINF = std::numeric_limits<long long>::max(); int t, n, m; std::cin >> t >> n >> m; if (t == 0) { std::vector<emthrm::Edge<long long>> edges; while (m--) { int u, v, w; std::cin >> u >> v >> w; --u; --v; edges.emplace_back(u, v, w); } const long long ans = emthrm::girth_in_undirected_graph(n, edges, LINF); std::cout << (ans == LINF ? -1 : ans) << '\n'; } else if (t == 1) { std::vector<std::vector<emthrm::Edge<long long>>> graph(n); while (m--) { int u, v, w; std::cin >> u >> v >> w; --u; --v; graph[u].emplace_back(u, v, w); } const long long ans = emthrm::girth_in_directed_graph(graph, LINF); std::cout << (ans == LINF ? -1 : ans) << '\n'; } return 0; }