Lib/ワーシャルフロイド法(全点対最短経路)
code:cpp
void warshall_floyd_init(vector<vector<ll>> &dist,vector<vector<pair<ll,ll>>> &graph,vector<vector<ll>> &prev){
ll n = graph.size();
rep(i,n){
rep(j,graphi.size()){
chmin(disti[graphij.first],graphij.second);
}
}
rep(i,n) distii = 0;
rep(i,n){
rep(j,n){
previj = i;
}
}
}
void warshall_floyd(vector<vector<ll>> &dist,vector<vector<ll>> &prev){
ll n = dist.size();
rep(k,n){
rep(i,n){
rep(j,n){
if(distik + distkj < distij){
distij = distik + distkj;
previj = prevkj;
}
}
}
}
}
signed main(void){
vector<vector<ll>> dist(n,vector<ll>(n,inf));
vector<vector<pair<ll,ll>>> graph(n);
vector<vector<ll>> prev(n,vector<ll>(n,-1));//経路復元
warshall_floyd_init(dist,graph,prev);
warshall_floyd(dist,prev);
}
O(V^3)