其实没什么好说的，从点 i 到点 j ，除了直接一条边连接直通还可以通过别的边中转得到，这样就得到了一个类似dp的一个状态转移方程。但是注意：1.Floyd必须用邻接矩阵存图。2.不能解决负环问题。
#include <bits/stdc++.h> using namespace std; int main() { int e[10][10],k,i,j,n,m,t1,t2,t3; int inf=99999999; //用inf(infinity的缩写)存储一个我们认为的正无穷值 //读入n和m，n表示顶点个数，m表示边的条数 scanf("%d %d",&n,&m); //初始化 for(i=1;i<=n;i++) for(j=1;j<=n;j++) if(i==j) e[i][j]=0;//自己到自己当然不需要任何代价 else e[i][j]=inf;//其它没有直通边的都赋值为正无穷 //读入边 for(i=1;i<=m;i++) { scanf("%d %d %d",&t1,&t2,&t3); e[t1][t2]=t3;//邻接矩阵存图 } //Floyd-Warshall算法核心语句 for(k=1;k<=n;k++) for(i=1;i<=n;i++) for(j=1;j<=n;j++) if(e[i][j]>e[i][k]+e[k][j] ) e[i][j]=e[i][k]+e[k][j]; //输出最终的结果 for(i=1;i<=n;i++) { for(j=1;j<=n;j++) printf("%10d",e[i][j]); printf("\n"); } return 0; }
例题：洛谷P2910
代码（第一次自己写floyd就成功了）：
#include<iostream> #include<cstdio> #include<algorithm> #include<cstring> #include<cmath> using namespace std; int n,m,ans; int a[10010],d[110][110],f[110][110]; inline int read() { int x=0,f=1;char ch=getchar(); while (!isdigit(ch)){if (ch=='-') f=-1;ch=getchar();} while (isdigit(ch)){x=x*10+ch-48;ch=getchar();} return x*f; } void floyd() { for(int i=1;i<=n;i++) for(int j=1;j<=n;j++) f[i][j]=d[i][j]; for(int k=1;k<=n;k++) for(int i=1;i<=n;i++) for(int j=1;j<=n;j++) f[i][j]=min(f[i][j],f[i][k]+f[k][j]); } int main() { n=read(); m=read(); for(int i=1;i<=m;i++) a[i]=read(); for(int i=1;i<=n;i++) for(int j=1;j<=n;j++) d[i][j]=read(); floyd(); for(int i=1;i<=m-1;i++) ans+=f[a[i]][a[i+1]]; printf("%d\n",ans); return 0; }
原文链接: https://www.cnblogs.com/57xmz/p/13204110.html
欢迎关注
微信关注下方公众号，第一时间获取干货硬货；公众号内回复【pdf】免费获取数百本计算机经典书籍;
也有高质量的技术群，里面有嵌入式、搜广推等BAT大佬
原创文章受到原创版权保护。转载请注明出处：https://www.ccppcoding.com/archives/360060
非原创文章文中已经注明原地址，如有侵权，联系删除
关注公众号【高性能架构探索】，第一时间获取最新文章
转载文章受原作者版权保护。转载请注明原作者出处！
