先来看一组样例
Input
5 8 1 4 5 1 3 2 3 4 3 4 2 2 4 5 1 1 5 8 2 5 4 3 2 6Output
0 7 2 5 6 -1 0 -1 -1 4 -1 5 0 3 4 -1 2 -1 0 1 -1 -1 -1 -1 0我们先将dis全部变成极大值（很重要）
但是如果i = j，dis[i][j] = 0;
我们不妨顺着代码的执行来手动模拟一下（前方高能！！！）
这个可真难画，将就着看吧。
k = 1 :
以1为中间节点来扩展
按照代码中写的来看，我们看到以1为中间节点可以扩展出从1到3，1到4，1到5的值。
此时已经没有点可以与1相连。
以2为中间节点的时候，这时候1和2还不能直接相连。所以不能扩展。
再看别的能扩展的i 和 j，
如下图我们可以更新3->2->5和4->2->5;
k = 3 :
从1到2的路径为极大值，如果通过3到达2，长度为8，8<=INF，所以dis[1][2]更新成8。
同理，dis[1][4] = 5;
此时，以3为中间节点的操作已经完成。
后面就不画图了，自行脑补吧
k = 4 :
可以通过4更新1->4->5 , 3->4->5 , 1->4->2 , 3->4->2.
同理，我们就可以把所有的点都更新完。
完整代码
#include <iostream> #include <cstdio> #include <cmath> #include <cstring> #define INF 214748364 using namespace std; int n, m, s, t; int dis[1005][1005]; int main() { scanf("%d%d", &n, &m); for(int i=1; i<=n; i++) { for(int j=1; j<=n; j++) { dis[i][j] = (i == j)?0:INF; } } for(int i=1; i<=m; i++) { int u, v, w; scanf("%d%d%d", &u, &v, &w); dis[u][v] = w; } for(int k=1; k<=n; k++) { for(int i=1; i<=n; i++) { for(int j=1; j<=n; j++) { if(dis[i][j] > dis[i][k]+dis[k][j]) { dis[i][j] = dis[i][k]+dis[k][j]; } } } } for(int i=1; i<=n; i++) { for(int j=1; j<=n; j++) { if(dis[i][j] != INF) printf("%d ", dis[i][j]); else printf("-1 "); } printf("\n"); } } 作者：wlz 出处：http://www.cnblogs.com/bljfy/p/8696334.html 本文版权归作者和博客园共有，欢迎转载，但未经作者同意必须保留此段声明，且在文章页面明显位置给出原文连接，否则保留追究法律责任的权利。转载于:https://www.cnblogs.com/bljfy/p/8696334.html
相关资源：数据结构—成绩单生成器