网站写动态新闻有什么好处,网站建设公司与维护,网站建设与维护是做什么,网站专栏怎么做漂亮目录
Floyd求最短路
854. Floyd求最短路 - AcWing题库
模板】Floyd
B3647 【模板】Floyd - 洛谷 | 计算机科学教育新生态 (luogu.com.cn) Floyd求最短路
854. Floyd求最短路 - AcWing题库
思路#xff1a;在代码里面
完整代码#xff1a;
#include bits/stdc.h在代码里面
完整代码
#include bits/stdc.h
#define int long long
signed main()
{int n,m,t;std::cin n m t;int dist[n1][n1];//初始化for(int i 1;i n;i ){for(int j 1;j n;j ){if (ij){dist[i][j]0;}else{dist[i][j]INT_MAX;}}}for(int i 1;i m;i ){int u,v,w;std::cin u v w;dist[u][v]std::min(dist[u][v],w);// u 到 v 的边权重为w,但是注意可能有多条边,取最小}for(int k 1;k n;k )//枚举中间点{for(int i 1;i n;i )//枚举起点{for(int j 1;j n;j )//枚举终点{dist[i][j]std::min(dist[i][j],dist[i][k]dist[k][j]);}}}while(t --){int x,y;std::cin x y;if(dist[x][y]INT_MAX/10)// 因为有负数边可能会轻微改变INT_MAX的值,但其实并不能达到,所以不能判断是否等于INT_MAX,如果没有负数边则可以直接判断std::coutimpossible\n;elsestd::coutdist[x][y]\n;}return 0;
}
模板】Floyd
B3647 【模板】Floyd - 洛谷 | 计算机科学教育新生态 (luogu.com.cn)
思路用floyd算法
注意是无向边需要建立一个双向边
完整代码
#include bits/stdc.h
#define int long long
signed main()
{int n,m;std::cin n m;int dist[n1][n1];for(int i 1;i n;i ){for(int j 1;j n;j ){if(ij){dist[i][j]0;dist[j][i]0;}else{dist[i][j]INT_MAX;dist[j][i]INT_MAX;}}}for(int i 1;i m;i ){int u,v,w;std::cin u v w;dist[u][v]std::min(dist[u][v],w);dist[v][u]std::min(dist[v][u],w);}for(int k 1;k n;k ){for(int i 1;i n;i ){for(int j 1;j n;j ){dist[i][j]std::min(dist[i][j],dist[i][k]dist[k][j]);dist[j][i]std::min(dist[j][i],dist[k][i]dist[j][k]);}}}for(int i 1;i n;i ){for(int j 1;j n;j ){std::coutdist[i][j] ;}std::cout\n;}return 0;
}
