C++ Library for Competitive Programming
/*
* @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;
}