shopify建站,网站建设安全协议,html5 网站框架,凡科建站网站建设2.6 1.蓝桥公园 2.路径 3.打印路径 4.【模板】Floyd
Floyd算法#xff1a;
是一种多源的最短路径算法#xff0c;经过一次计算可以得到任意两个点之间的最短路径。
这种算法是基于动态规划的思想#xff1a;
m[i][j]表示从i到j这条边的距离#xff0c;dp[k][i][j]表示从…2.6 1.蓝桥公园 2.路径 3.打印路径 4.【模板】Floyd
Floyd算法
是一种多源的最短路径算法经过一次计算可以得到任意两个点之间的最短路径。
这种算法是基于动态规划的思想
m[i][j]表示从i到j这条边的距离dp[k][i][j]表示从i到j且经过{0,1,...,k-1}中若干点的最短路径。
那么转移方程就就是dp[k][i][j]min(dp[k−1][i][j],dp[k−1][i][k]dp[k−1][k][j])这表示了比较经过k和不经过k两种的情况的路径找到较小值 例如在k1的时候 d p [ 1 ] [ i ] [ j ] m i n ( d p [ 0 ] [ i ] [ j ] , d p [ 0 ] [ i ] [ 1 ] d p [ 0 ] [ 1 ] [ j ] ) m i n ( m [ i ] [ j ] , m [ i ] [ 1 ] m [ 1 ] [ j ] )
通过滚动数组我们可以优化dp数组的空间将他从三维的数组变成二维的
dp[i][j]min(dp[i][j],dp[i][k]dp[k][j])
与其他最短路径相比Floyd算法有以下几点特点
1.可以找到所有节点之间的最短距离
2.代码简单就三重循环
3.效率比较低是On^3的时间复杂度
这是算法的模版
void floyd(){for (int k1;kn;k){for (int i1;in;i){for (int j1;jn;j){if(i!j)dp[i][j]min(dp[i][j],dp[i][k]dp[k][j]);else dp[i][j]dp[j][i]0;}}}
}
蓝桥公园https://www.lanqiao.cn/problems/1121/learning/?page1first_category_id1status2
#include bits/stdc.h
using namespace std;
#define lowbit(x) (x - (x))
#define int long long
const int INF0x3f3f3f3f3f3f3f3fll;
const int N405;
int dp[N][N];
int n,m,q;
void input(){memset(dp,0x3f,sizeof(dp));for (int i1;im;i){int u,v,w;cinuvw;dp[u][v]dp[v][u]min(dp[u][v],w);}
}
void fioyd(){for (int k1;kn;k){for (int i1;in;i){for (int j1;jn;j){dp[i][j]min(dp[i][j],dp[i][k]dp[k][j]);}}}
}
void output(){while (q--){int s,t; cinst;if (st) cout0endl;else if (dp[s][t]INF) cout-1endl;else coutdp[s][t]endl;}
}
signed main(){cinnmq;input(); fioyd(); output();return 0;
}路径https://www.lanqiao.cn/problems/1460/learning/?page1first_category_id1problem_id1460
#include bits/stdc.h
using namespace std;
#define lowbit(x) (x - (x))
#define int long long
const int INF0x3f3f3f3f;
const int N2050;
int dp[N][N];
int gcd(int a,int b){if (b0) return a;return gcd(b,a%b);
}
void floyd(){for (int k1;k2021;k){for (int i1;i2021;i){for (int j1;j2021;j){dp[i][j]min(dp[i][j],dp[i][k]dp[k][j]);}}}
}
signed main(){for (int i1;i2021;i){for (int ji1;j2021;j){if (abs(i-j)21){dp[i][j]dp[j][i]INF;}else if (abs(i-j)21){dp[i][j]dp[j][i](i*j)/gcd(i,j);}}}floyd();coutdp[1][2021];
}打印路径https://www.lanqiao.cn/problems/1656/learning/?page1first_category_id1problem_id1656
这道题需要的点比较多需要记录最短路径还有每个 城市都会收税记录最短路径的话就再建一个二维数组记录每个点之间的关系
#include bits/stdc.h
using namespace std;
#define lowbit(x) (x - (x))
#define int long long
const int INF0x3f3f3f3f;
const int N505;
int n;
int dp[N][N],shui[N],path[N][N];
void input(){cinn;for (int i1;in;i){for (int j1;jn;j){int x; cinx;if (x-1) dp[i][j]dp[j][i]INF;else{dp[i][j]dp[j][i]x;}path[i][j]j;}}for (int i1;in;i) cinshui[i];
}
void floyd(){for (int k1;kn;k){for (int i1;in;i){for (int j1;jn;j){if (dp[i][j]dp[i][k]dp[k][j]shui[k]){dp[i][j]dp[i][k]dp[k][j]shui[k];path[i][j]path[i][k];}else if (dp[i][k]dp[k][j]shui[k]dp[i][j] path[i][k]path[i][j]){dp[i][j]dp[i][k]dp[k][j]shui[k];path[i][j]path[i][k];}}}}
}
void output(){int s,t;while (cinst){if (s-1 t-1)break;coutFrom s to t :endl;coutPath: s;int idxs;while (idx!t){idxpath[idx][t];cout--idx;}coutendl;coutTotal cost : dp[s][t]endlendl;}
}
signed main(){input(); floyd(); output();return 0;
}【模板】Floydhttps://www.luogu.com.cn/problem/B3647
题目描述
给出一张由 n 个点 m 条边组成的无向图。
求出所有点对 (,)(i,j) 之间的最短路径。
输入格式
第一行为两个整数 ,n,m分别代表点的个数和边的条数。
接下来 m 行每行三个整数 ,,u,v,w代表 ,u,v 之间存在一条边权为 w 的边。
输出格式
输出 n 行每行 n 个整数。
第 i 行的第 j 个整数代表从 i 到 j 的最短路径。
输入输出样例
输入 #1复制
4 4
1 2 1
2 3 1
3 4 1
4 1 1
输出 #1复制
0 1 2 1
1 0 1 2
2 1 0 1
1 2 1 0
说明/提示
对于 100%100% 的数据≤100n≤100≤4500m≤4500任意一条边的权值 w 是正整数且 1⩽⩽10001⩽w⩽1000。
数据中可能存在重边。
#include bits/stdc.h
using namespace std;
#define lowbit(x) (x - (x))
#define int long long
const int INF0x3f3f3f3f;
const int N505;
int n,m;
int dp[N][N];
void floyd(){for (int k1;kn;k){for (int i1;in;i){for (int j1;jn;j){if(i!j)dp[i][j]min(dp[i][j],dp[i][k]dp[k][j]);else dp[i][j]dp[j][i]0;}}}
}
signed main(){cinnm;memset(dp,INF,sizeof(dp));for (int i1;im;i){int a,b,c;cinabc;dp[a][b]dp[b][a]min(dp[a][b],c); //防止重边 }floyd();for (int i1;in;i){for (int j1;jn;j){coutdp[i][j] ;}coutendl;}return 0;
}
