floyd模板

B3647 【模板】Floyd - 洛谷

$floyd$ 模板

对于 $floyd$ 算法来说时间复杂度为 $O(n^3)$ ，不如跑 $n$ 遍 $heap\_dijkstra$ 算法

题目大意：

给出一张由 $n$ 个点 $m$ 条边组成的无向图，求出所有点对 $(i,j)$ 之间的最短路径

思路：

设 $D[k,i,j]$ 表示经过若干个不超过 $k$ 的节点，从 $i$ 到 $j$ 的最短路径

考虑转移可由 状态为 $k-1$ 的节点，从 $i$ 到 $k$ ，再到 $j$

$k$ 是阶段，置于外循环，每次都尝试用 $k$ 更新 $i$ 到 $j$ 即可

for(int k=1;k<=n;k++){for(int i=1;i<=n;i++){for(int j=1;j<=n;j++){d[i][j]=max(d[i][j],d[i][k]+d[k][j]);}}
}

代码：

#include <bits/stdc++.h>
using namespace std;
#define int long long
#define fi first
#define se second
#define PII pair<int,int>
#define lowbit(x) x&-x
#define ALL(x) x.begin(),x.end()const int mod = 1e9 + 7;
const int N = 1e3+10;int n,m;
int d[N][N];void floyd() {for(int k=1;k<=n;k++) {for(int i=1;i<=n;i++) {for(int j=1;j<=n;j++) {d[i][j]=min(d[i][j],d[i][k]+d[k][j]);}}}
}void solve() {cin>>n>>m;for(int i=1;i<=n;i++){for(int j=1;j<=n;j++){d[i][j]=1e18;if(i==j){d[i][j]=0;}}}for(int i=1;i<=m;i++){int u,v,x;cin>>u>>v>>x;d[u][v]=min(d[u][v],x);d[v][u]=min(d[v][u],x);}floyd();for(int i=1;i<=n;i++){for(int j=1;j<=n;j++){cout<<d[i][j]<<" ";}cout<<'\n';}}signed main() {std::ios::sync_with_stdio(0);cin.tie(0);cout.tie(0);int T = 1;
//	cin >> T;while (T--) {solve();}return 0;
}