mmrz's library

This documentation is automatically generated by online-judge-tools/verification-helper

---

Project maintained by mm-rz Hosted on GitHub Pages — Theme by mattgraham

全頂点間最短距離 O(V^3) 及び更新を O(V^2) で行うアルゴリズム (ワーシャルフロイド法)
(graph/warshall_floyd.hpp)

• View this file on GitHub
• Last update: 2025-07-01 03:22:56+09:00
• Include: #include "graph/warshall_floyd.hpp"

全頂点間最短距離 O(V^3) 及び更新を O(V^2) で行うアルゴリズム (ワーシャルフロイド法)

使い方

• warshall_floyd(vector<vector<T>> &edge_cost, T infty=::numeric_limits<T>()/2) : コンストラクタ。距離行列を用意する。
  • 全頂点間最短距離を格納した行列 dist が $O(V^3)$ で求まる。
  • ただし、 edge_cost[i][i] = 0, 結ばれていない頂点間は $\text{infty}$ を格納すること($2 \times \text{infty} < \text(型 T の最大値)$ である必要がある)
• void update(int s, int t, T, cost) : edge_cost[s][t] を cost に更新する。 $O(V^2)$

Verified with

• verify/aoj/id/0526.test.cpp
• verify/aoj/id/2005.test.cpp

Code

#pragma once

#include<numeric>
#include<vector>

template<typename T>
struct warshall_floyd {
private:
	int V;
public:
	std::vector<std::vector<T>> dist;

	warshall_floyd(std::vector<std::vector<T>> &edge_cost, T infty=std::numeric_limits<T>::max()/2) : V(ssize(edge_cost)), dist(edge_cost){
		for(int k = 0;k < V;k++){
			for(int i = 0;i < V;i++){
				if(dist[i][k] == infty)continue;
				for(int j = 0;j < V;j++){
					if(dist[k][j] == infty)continue;
					dist[i][j] = min(dist[i][j], dist[i][k] + dist[k][j]);
				}
			}
		}
	}

	void update(int s, int t, T cost){
		dist[s][t] = cost;
		for(int u = 0;u < V;u++){
			for(int v = 0;v < V;v++){
				dist[u][v] = min(dist[u][v], dist[u][s]+dist[s][t]+dist[t][v]);
			}
		}
	}
};

#line 2 "graph/warshall_floyd.hpp"

#include<numeric>
#include<vector>

template<typename T>
struct warshall_floyd {
private:
	int V;
public:
	std::vector<std::vector<T>> dist;

	warshall_floyd(std::vector<std::vector<T>> &edge_cost, T infty=std::numeric_limits<T>::max()/2) : V(ssize(edge_cost)), dist(edge_cost){
		for(int k = 0;k < V;k++){
			for(int i = 0;i < V;i++){
				if(dist[i][k] == infty)continue;
				for(int j = 0;j < V;j++){
					if(dist[k][j] == infty)continue;
					dist[i][j] = min(dist[i][j], dist[i][k] + dist[k][j]);
				}
			}
		}
	}

	void update(int s, int t, T cost){
		dist[s][t] = cost;
		for(int u = 0;u < V;u++){
			for(int v = 0;v < V;v++){
				dist[u][v] = min(dist[u][v], dist[u][s]+dist[s][t]+dist[t][v]);
			}
		}
	}
};

Back to top page