例题链接(这道题也可以用Dijkstra做):https://vjudge.net/contest/341090#problem/A
Floyd的优点:
1.代码短
2.可以带负值
3.最后mp[i][j]存的是从i到j的最短路,并不是单源最短路
缺点:
三层for循环,时间复杂度是O(n^3),比Dijkstra的事件复杂度大挺多的。
#include <cstdio> #include <iostream> #include <cstring> #include <string> using namespace std; #define MAX 0x3f3f3f3 int m,n,a,b,c; int mp[105][105]; int main () { while (cin >> m >> n) { if(m==0&&n==0)break; for (int i=1;i<=m;i++) { for (int j=1;j<=m;j++) { mp[i][j]=MAX; } } for (int i=1;i<=n;i++) { cin >> a >> b >> c; mp[a][b]=mp[b][a]=c; } for (int k=1;k<=m;k++) //k为中间节点 { for (int i=1;i<=m;i++) { for (int j=1;j<=m;j++) { if(mp[i][j]>mp[i][k]+mp[k][j]) { mp[i][j]=mp[i][k]+mp[k][j]; } } } } cout << mp[1][m] << endl; } return 0; }