网站建设套餐自助报价,建材在哪里做网站好,企业网站建设空间,ueditor to wordpressFloyd算法#xff1a; 标准弗洛伊德算法#xff0c;三重循环#xff0c;基于动态规划。 循环结束之后 d[i][j]存储的就是点 i 到点 j 的最短距离。 需要注意循环顺序不能变#xff1a;第一层枚举中间点#xff0c;第二层和第三层枚举起点和终点。 特点#xff1a; 1.复杂…Floyd算法 标准弗洛伊德算法三重循环基于动态规划。 循环结束之后 d[i][j]存储的就是点 i 到点 j 的最短距离。 需要注意循环顺序不能变第一层枚举中间点第二层和第三层枚举起点和终点。 特点 1.复杂度为On^3只能处理200以内的点。 2.一次求出所有结点直接的最短路径。 3.能处理有负权边的图。 Floyd模板
#includebits/stdc.h
using namespace std;
const int INF0x3f3f3f3f;
const int N205;
int n,m,d[N][N];
int main(){scanf(%d%d%d,n,m);//初始化 for(int i1;in;i) for(int j1;jn;j)d[i][j]ij?0:INF; //自己到自己的距离为0 //输入边 for(int i0,x,y,w;im;i){scanf(%d%d%d,x,y,x);d[x][y]d[y][x]min(d[x][y],w);}//Floyd核心代码 for(int k1;kn;k){for(int i1;in;i){for(int j1;jn;j){
// if(d[i][k]INF||d[k][j]INF) continue; //防止负权影响INF if(d[i][j]d[i][k]d[k][j])d[i][j]d[i][k]d[k][j];
// e[i][j]min(e[i][j],e[i][k]e[k][j]); //数据量大时min会慢一些 }}}coutd[1][n];return 0;
} AcWing 854. Floyd求最短路
给定一个 nn 个点 mm 条边的有向图图中可能存在重边和自环边权可能为负数。
再给定 kk 个询问每个询问包含两个整数 xx 和 yy表示查询从点 xx 到点 yy 的最短距离如果路径不存在则输出 impossible。
数据保证图中不存在负权回路。
输入格式 第一行包含三个整数 n,m,kn,m,k。 接下来 mm 行每行包含三个整数 x,y,zx,y,z表示存在一条从点 xx 到点 yy 的有向边边长为 zz。 接下来 kk 行每行包含两个整数 x,yx,y表示询问点 xx 到点 yy 的最短距离。 输出格式 共 kk 行每行输出一个整数表示询问的结果若询问两点间不存在路径则输出 impossible。 数据范围 1≤n≤200 1≤n≤200, 1≤k≤n2 1≤k≤n2 1≤m≤20000 1≤m≤20000, 图中涉及边长绝对值均不超过 1000010000。 输入样例
3 3 2
1 2 1
2 3 2
1 3 1
2 1
1 3输出样例
impossible
1
代码
#includebits/stdc.h
using namespace std;
const int INF0x3f3f3f3f;
const int N205;
int n,m,k,x,y,z,e[N][N];
int main(){scanf(%d%d%d,n,m,k);for(int i1;in;i) //初始化 for(int j1;jn;j)e[i][j]ij?0:INF;for(int i0;im;i){scanf(%d%d%d,x,y,z);e[x][y]min(e[x][y],z);}for(int k1;kn;k){for(int i1;in;i){for(int j1;jn;j){if(e[i][k]INF||e[k][j]INF) continue; //防止负权影响INF或者在输出的时候判断e[x][y]INF/2 if(e[i][j]e[i][k]e[k][j])e[i][j]e[i][k]e[k][j];
// e[i][j]min(e[i][j],e[i][k]e[k][j]); //数据量大时min会慢一些 }}}while(k--){scanf(%d%d,x,y);if(e[x][y]INF) coutimpossibleendl; //存在负权时如果不存在通路不一定是INF会小一些 else coute[x][y]endl;}return 0;
}
