Floyd 学习笔记

#include <cstdio> #include <cstring> #include <ctype.h> #include <cstdlib> #include <cmath> #include <climits> #include <ctime> #include <iostream> #include <algorithm> #include <deque> #include <vector> #include <queue> #include <string> #include <map> #include <stack> #include <set> #include <list> #include <numeric> #include <sstream> #include <iomanip> #include <limits> #define CLR(a, b) memset(a, (b), sizeof(a)) #define pb push_back #define debug puts("***debug***"); using namespace std; typedef long long ll; typedef long double ld; typedef unsigned long long ull; typedef pair <int, int> pii; typedef pair <ll, ll> pll; typedef pair<string, int> psi; typedef pair<string, string> pss; const double PI = acos(-1.0); const double E = exp(1.0); const double eps = 1e-30; const int INF = 0x3f3f3f3f; const int maxn = 3e2 + 10; const int MOD = 1e9 + 7; int G[maxn][maxn]; int n; void Floyd() { // 如果两个点之间能够有更短的路径 那么必然要引入第三个点 来进行路径转移 // 假如我们借助第0个点来转移 // 那么我们应该这么写 // for (int i = 0; i < n; i++) // for (int i = 0; i < n; i++) // if (G[i][j] > G[i][0] + G[0][j]) // G[i][j] = G[i][0] + G[0][j]; // 由于第0个点已经经过转移后的最优状态了，那么我们通过第1个点来转移的时候， // 如果第1个点中有的点是经过第0个点转移的 那么 我们通过第1个点转移，实际上 // 是先通过第0个点 再经过第1个点转移 // 代码应该这么写 // for (int i = 0; i < n; i++) // for (int i = 0; i < n; i++) // if (G[i][j] > G[i][1] + G[1][j]) // G[i][j] = G[i][1] + G[1][j]; // 其实可以知道 每次转移 都是往下面的点转移的 那么可以直接用个FOR 来表示 就是下面的代码 for (int k = 0; k < n; k++) for (int i = 0; i < n; i++) for (int j = 0; j < n; j++) if (G[i][j] > G[i][k] + G[k][j]) G[i][j] = G[i][k] + G[k][j]; } int main() { scanf("%d", &n); // input for (int i = 0; i < n; i++) for (int j = 0; j < n; j++) scanf("%d", &G[i][j]); Floyd(); // output for (int i = 0; i < n; i++) { for (int j = 0; j < n; j++) printf("%d", &G[i][j]); cout << endl; } }

转载于:https://www.cnblogs.com/Dup4/p/9433090.html

相关资源：Dijkstra、Floyd算法Matlab,Lingo实现