106 lines
2.6 KiB
C++
106 lines
2.6 KiB
C++
|
/* #define NDEBUG */
|
||
|
|
|
||
|
|
#include <stdlib.h>
|
||
|
|
/* #include <string> */
|
||
|
|
#include <vector>
|
||
|
|
/* #include <array> */
|
||
|
|
/* #include <queue> */
|
||
|
|
#include <iostream>
|
||
|
|
/* #include <map> */
|
||
|
|
/* #include <math.h> */
|
||
|
|
/* #include <numeric> */
|
||
|
|
/* #include <tuple> */
|
||
|
|
/* #include <set> */
|
||
|
|
#include <limits>
|
||
|
|
|
||
|
|
using namespace std;
|
||
|
|
|
||
|
|
|
||
|
|
|
||
|
|
template <typename T>
|
||
|
|
class adjacency_list {
|
||
|
|
public:
|
||
|
|
size_t N;
|
||
|
|
std::vector<std::vector<T>> adj;
|
||
|
|
|
||
|
|
adjacency_list (size_t n) {
|
||
|
|
N = n;
|
||
|
|
adj(N, std::vector<T>());
|
||
|
|
}
|
||
|
|
|
||
|
|
std::vector<T> operator[](T i) { adj[i]; };
|
||
|
|
void add_directed_edge(size_t i, size_t j) {
|
||
|
|
adj[i].push_back(j);
|
||
|
|
};
|
||
|
|
void add_undirected_edge(size_t i, size_t j) {
|
||
|
|
adj[i].push_back(j);
|
||
|
|
adj[j].push_back(i);
|
||
|
|
};
|
||
|
|
};
|
||
|
|
|
||
|
|
template <typename T = long>
|
||
|
|
std::vector<std::vector<T>> floyd_warshall(std::vector<std::vector<T>> adj);
|
||
|
|
|
||
|
|
|
||
|
|
int main() {
|
||
|
|
vector<vector<int>> adj_matrix;
|
||
|
|
auto foo = floyd_warshall(adj_matrix);
|
||
|
|
/* floyd_warshall<int>(adj_matrix); */
|
||
|
|
;
|
||
|
|
|
||
|
|
return EXIT_SUCCESS;
|
||
|
|
}
|
||
|
|
|
||
|
|
#ifndef NDEBUG
|
||
|
|
#endif
|
||
|
|
|
||
|
|
// NOTE: !!!UNTESTED!!!
|
||
|
|
// Time complexity: O(n^3)
|
||
|
|
// Memory complexity: O(n^2) - only for n ~ 10^3 (n ~ 10^4 results in 1524 MB of memory)
|
||
|
|
// Input: Graph as an adjancency matrix (weight 0 => no edge)
|
||
|
|
// Output: A distance matrix (distance std::numeric_limits<T>::max() => no path)
|
||
|
|
#include <stdlib.h>
|
||
|
|
#include <limits>
|
||
|
|
#include <vector>
|
||
|
|
#include <algorithm>
|
||
|
|
template <typename T>
|
||
|
|
std::vector<std::vector<T>> floyd_warshall(std::vector<std::vector<T>> adj) {
|
||
|
|
size_t n = adj.size();
|
||
|
|
std::vector<std::vector<long>> distance(n, std::vector<T>(n, 0));
|
||
|
|
|
||
|
|
// Initialize distance
|
||
|
|
for (size_t i = 0; i < n; i++) {
|
||
|
|
for (size_t j = 0; j < n; j++) {
|
||
|
|
if (i == j) distance[i][j] = 0;
|
||
|
|
else if (adj[i][j]) distance[i][j] = adj[i][j];
|
||
|
|
else distance[i][j] = std::numeric_limits<T>::max();
|
||
|
|
}
|
||
|
|
}
|
||
|
|
|
||
|
|
// Find shortest distances
|
||
|
|
for (size_t k = 0; k < n; k++) {
|
||
|
|
for (size_t i = 0; i < n; i++) {
|
||
|
|
for (size_t j = 0; j < n; j++) {
|
||
|
|
if (distance[i][k] == std::numeric_limits<T>::max() || distance[k][j] == std::numeric_limits<T>::max())
|
||
|
|
continue;
|
||
|
|
distance[i][j] = std::min(distance[i][j],
|
||
|
|
distance[i][k] + distance[k][j]);
|
||
|
|
}
|
||
|
|
}
|
||
|
|
}
|
||
|
|
|
||
|
|
return distance;
|
||
|
|
}
|
||
|
|
|
||
|
|
|
||
|
|
|
||
|
|
template <typename T = long>
|
||
|
|
class 1D_sum_queries {
|
||
|
|
vector<vector<T>> array;
|
||
|
|
public:
|
||
|
|
1D_sum_queries(size_t n) {
|
||
|
|
|
||
|
|
}
|
||
|
|
std::vector<T> operator[](T i) { adj[i]; };
|
||
|
|
}
|