shortest_routes_ii_1672.cpp (732B)
1 #include <algorithm> 2 #include <iostream> 3 #include <vector> 4 5 constexpr size_t inf{999999999999999ULL}; 6 7 int main() { 8 size_t n, m, q; 9 std::cin >> n >> m >> q; 10 std::vector<std::vector<size_t>> d(n, std::vector(n, inf)); 11 for (size_t i = 0; i < n; i++) d[i][i] = 0; 12 for (size_t i = 0; i < m; i++) { 13 size_t x, y, z; 14 std::cin >> x >> y >> z; 15 d[x-1][y-1] = d[y-1][x-1] = std::min(d[x-1][y-1], z); 16 } 17 18 for (size_t k = 0; k < n; k++) 19 for (size_t i = 0; i < n; i++) 20 for (size_t j = 0; j < n; j++) 21 d[j][i] = d[i][j] = 22 std::min(d[i][j], d[i][k] + d[k][j]); 23 24 for (size_t i = 0; i < q; i++) { 25 size_t x, y; 26 std::cin >> x >> y; 27 long long int dd = d[x-1][y-1]; 28 std::cout << (dd == inf ? -1LL : dd) << "\n"; 29 } 30 }