From 96254947699986c59f0dc63d69fd4b76bd3ed43e Mon Sep 17 00:00:00 2001 From: Sebastiano Tronto Date: Mon, 6 Jul 2026 19:08:08 +0200 Subject: Initial commit --- 04_graph_algorithms/shortest_routes_ii_1672.cpp | 30 +++++++++++++++++++++++++ 1 file changed, 30 insertions(+) create mode 100644 04_graph_algorithms/shortest_routes_ii_1672.cpp (limited to '04_graph_algorithms/shortest_routes_ii_1672.cpp') diff --git a/04_graph_algorithms/shortest_routes_ii_1672.cpp b/04_graph_algorithms/shortest_routes_ii_1672.cpp new file mode 100644 index 0000000..d49cb71 --- /dev/null +++ b/04_graph_algorithms/shortest_routes_ii_1672.cpp @@ -0,0 +1,30 @@ +#include +#include +#include + +constexpr size_t inf{999999999999999ULL}; + +int main() { + size_t n, m, q; + std::cin >> n >> m >> q; + std::vector> d(n, std::vector(n, inf)); + for (size_t i = 0; i < n; i++) d[i][i] = 0; + for (size_t i = 0; i < m; i++) { + size_t x, y, z; + std::cin >> x >> y >> z; + d[x-1][y-1] = d[y-1][x-1] = std::min(d[x-1][y-1], z); + } + + for (size_t k = 0; k < n; k++) + for (size_t i = 0; i < n; i++) + for (size_t j = 0; j < n; j++) + d[j][i] = d[i][j] = + std::min(d[i][j], d[i][k] + d[k][j]); + + for (size_t i = 0; i < q; i++) { + size_t x, y; + std::cin >> x >> y; + long long int dd = d[x-1][y-1]; + std::cout << (dd == inf ? -1LL : dd) << "\n"; + } +} -- cgit v1.3