グラフ/最短路問題/Warshall–Floyd 法
(test/graph/shortest_path/warshall-floyd.test.cpp)

• View this file on GitHub
• Last update: 2023-02-25 01:48:23+09:00
• Problem: http://judge.u-aizu.ac.jp/onlinejudge/description.jsp?id=0526

Depends on

• Warshall–Floyd 法 (include/emthrm/graph/shortest_path/warshall-floyd.hpp)

Code

/*
 * @title グラフ/最短路問題/Warshall–Floyd 法
 *
 * verification-helper: PROBLEM http://judge.u-aizu.ac.jp/onlinejudge/description.jsp?id=0526
 */

#include <iostream>
#include <vector>

#include "emthrm/graph/shortest_path/warshall-floyd.hpp"

int main() {
  constexpr long long LINF = 0x3f3f3f3f3f3f3f3fLL;
  while (true) {
    int n, k;
    std::cin >> n >> k;
    if (n == 0 && k == 0) [[unlikely]] break;
    std::vector<std::vector<long long>> graph(n,
                                              std::vector<long long>(n, LINF));
    for (int i = 0; i < n; ++i) {
      graph[i][i] = 0;
    }
    emthrm::WarshallFloyd<long long> warshall_floyd(graph, LINF);
    while (k--) {
      int type;
      std::cin >> type;
      if (type == 0) {
        int a, b;
        std::cin >> a >> b;
        --a; --b;
        std::cout << (warshall_floyd.dist[a][b] == LINF ?
                      -1 : warshall_floyd.dist[a][b])
                  << '\n';
      } else if (type == 1) {
        int c, d;
        long long e;
        std::cin >> c >> d >> e;
        --c; --d;
        warshall_floyd.add(c, d, e);
        warshall_floyd.add(d, c, e);
        warshall_floyd.calc();
      }
    }
  }
  return 0;
}

#line 1 "test/graph/shortest_path/warshall-floyd.test.cpp"
/*
 * @title グラフ/最短路問題/Warshall–Floyd 法
 *
 * verification-helper: PROBLEM http://judge.u-aizu.ac.jp/onlinejudge/description.jsp?id=0526
 */

#include <iostream>
#include <vector>

#line 1 "include/emthrm/graph/shortest_path/warshall-floyd.hpp"



#include <algorithm>
#include <iterator>
#line 7 "include/emthrm/graph/shortest_path/warshall-floyd.hpp"

namespace emthrm {

template <typename T>
struct WarshallFloyd {
  std::vector<std::vector<T>> graph, dist;

  WarshallFloyd(const std::vector<std::vector<T>>& graph, const T inf)
      : graph(graph), dist(graph), inf(inf), n(graph.size()),
        internal(n, std::vector<int>(n, -1)) {
    for (int k = 0; k < n; ++k) {
      for (int i = 0; i < n; ++i) {
        for (int j = 0; j < n; ++j) {
          if (dist[i][k] + dist[k][j] < dist[i][j]) {
            dist[i][j] = dist[i][k] + dist[k][j];
            internal[i][j] = k;
          }
        }
      }
    }
  }

  void add(const int src, const int dst, const T cost) {
    srcs.emplace_back(src);
    dsts.emplace_back(dst);
    costs.emplace_back(cost);
  }

  void calc() {
    const int m = srcs.size();
    for (int i = 0; i < m; ++i) {
      graph[srcs[i]][dsts[i]] = std::min(graph[srcs[i]][dsts[i]], costs[i]);
      if (costs[i] <= dist[srcs[i]][dsts[i]]) {
        dist[srcs[i]][dsts[i]] = costs[i];
        internal[srcs[i]][dsts[i]] = -1;
      }
    }
    std::vector<int> vers(m * 2);
    std::copy(srcs.begin(), srcs.end(), vers.begin());
    std::copy(dsts.begin(), dsts.end(), std::next(vers.begin(), m));
    std::sort(vers.begin(), vers.end());
    vers.erase(std::unique(vers.begin(), vers.end()), vers.end());
    for (const int ver : vers) {
      for (int i = 0; i < n; ++i) {
        for (int j = 0; j < n; ++j) {
          if (dist[i][j] > dist[i][ver] + dist[ver][j]) {
            dist[i][j] = dist[i][ver] + dist[ver][j];
            internal[i][j] = ver;
          }
        }
      }
    }
    srcs.clear();
    dsts.clear();
    costs.clear();
  }

  bool has_negative_cycle() const {
    for (int i = 0; i < n; ++i) {
      if (dist[i][i] < 0) return true;
    }
    return false;
  }

  std::vector<int> build_path(const int s, const int t) const {
    std::vector<int> res;
    if (dist[s][t] != inf) {
      build_path(s, t, &res);
      res.emplace_back(t);
    }
    return res;
  }

 private:
  const T inf;
  const int n;
  std::vector<int> srcs, dsts;
  std::vector<T> costs;
  std::vector<std::vector<int>> internal;

  void build_path(const int s, const int t, std::vector<int>* path) const {
    const int k = internal[s][t];
    if (k == -1) {
      (*path).emplace_back(s);
    } else {
      build_path(s, k, path);
      build_path(k, t, path);
    }
  }
};

}  // namespace emthrm


#line 11 "test/graph/shortest_path/warshall-floyd.test.cpp"

int main() {
  constexpr long long LINF = 0x3f3f3f3f3f3f3f3fLL;
  while (true) {
    int n, k;
    std::cin >> n >> k;
    if (n == 0 && k == 0) [[unlikely]] break;
    std::vector<std::vector<long long>> graph(n,
                                              std::vector<long long>(n, LINF));
    for (int i = 0; i < n; ++i) {
      graph[i][i] = 0;
    }
    emthrm::WarshallFloyd<long long> warshall_floyd(graph, LINF);
    while (k--) {
      int type;
      std::cin >> type;
      if (type == 0) {
        int a, b;
        std::cin >> a >> b;
        --a; --b;
        std::cout << (warshall_floyd.dist[a][b] == LINF ?
                      -1 : warshall_floyd.dist[a][b])
                  << '\n';
      } else if (type == 1) {
        int c, d;
        long long e;
        std::cin >> c >> d >> e;
        --c; --d;
        warshall_floyd.add(c, d, e);
        warshall_floyd.add(d, c, e);
        warshall_floyd.calc();
      }
    }
  }
  return 0;
}

Back to top page