Advertisement
Not a member of Pastebin yet?
Sign Up,
it unlocks many cool features!
- #include <iostream>
- #include <vector>
- #include <algorithm>
- #include <iterator>
- #include <unordered_map>
- #include <functional>
- #include <unordered_set>
- #include <string>
- #include <set>
- #include <utility>
- #include <stack>
- #include <limits.h>
- std::vector<std::vector<long long>> matrix;
- int main() {
- long long N, a;
- std::cin >> N;
- std::vector<long long> line;
- for (int i = 0; i < N; i++) {
- for (int j = 0; j < N; j++) {
- std::cin >> a;
- if (a == 0) {
- line.push_back(LLONG_MAX);
- } else {
- line.push_back(a);
- }
- }
- matrix.push_back(line);
- line.clear();
- }
- long long result = 0;
- for (int n = 0; n < N; n++) {
- for (int i = 0; i < N; i++) {
- for (int j = 0; j < N; j++) {
- if (i != j) {
- if (matrix[i][n] != LLONG_MAX &&
- matrix[n][j] != LLONG_MAX) {
- matrix[i][j] = std::min(matrix[i][j],
- matrix[i][n] + matrix[n][j]);
- }
- }
- }
- }
- }
- for (int i = 0; i < N; i++) {
- for (int j = 0; j < N; j++) {
- if (matrix[i][j] != LLONG_MAX && matrix[i][j] > result) {
- result = matrix[i][j];
- }
- }
- }
- std::cout << result;
- }
Advertisement
Add Comment
Please, Sign In to add comment
Advertisement