因?yàn)闀r(shí)間復(fù)雜度為O(n^3)，所以可以使用頂點(diǎn)數(shù)為200以內(nèi)，創(chuàng)建鄰接矩陣在空間上也是可以的，而且每個(gè)點(diǎn)之間的數(shù)據(jù)都需要記錄，使用鄰接矩陣也是很好的。

設(shè)計(jì)思路：

1. 遍歷所有的點(diǎn)k
2. 以該點(diǎn)k為中介點(diǎn)，遍歷所有與它相鄰的點(diǎn)是否滿足dis[i][k]+dis[k][j]<dis[i][j]，滿足則覆蓋a[i][j]。

如果使用鄰接表，則dis[..][k]很難找，需要遍歷0-n-1的行才能找到所有的dis[..][k]。
dis[i][j]也是，操作比矩陣要復(fù)雜很多。

示例代碼：

測(cè)試數(shù)據(jù)：
4 5
1 2 1
1 3 2
1 4 5
2 4 3
3 4 1

image.png

主要數(shù)據(jù)結(jié)構(gòu)：

int dis[N][N]={0};           // 記錄到源點(diǎn)的距離
int points=0;                // 記錄點(diǎn)數(shù)

示例代碼：

#include <bits/stdc++.h>
using namespace std;
typedef struct{
  int num;      // 在BFS中第一列[0]中作為記錄上次遍歷的位置
  int length;    // 長(zhǎng)度
}Node;
const int INF=10000000;
#define N 200
int dis[N][N]={0};           // 記錄到源點(diǎn)的距離
int points=0;                // 記錄點(diǎn)數(shù)
int edges=0,begining,ending;
void Floyd(){
  int i,j,k;
  for(k=1;k<points+1;k++){
    for(i=1;i<points+1;i++){
      for(j=1;j<points;j++){
        if(dis[i][k]!=INF&&dis[k][j]!=INF&&dis[i][k]+dis[k][j]<dis[i][j]){
          // 如果同步到i>j的一面會(huì)導(dǎo)致實(shí)際更改未被打印，所以要把左側(cè)的結(jié)果同步到右側(cè)。
          dis[i][j]=dis[i][k]+dis[k][j];
          dis[j][i]=dis[i][k]+dis[k][j];
        }
      }
    }
  }
}
// 為了減少打印操作，只打印右半邊的數(shù)據(jù)
void show(){
  int i,j;
  for(i=1;i<points+1;i++){
    for(j=i+1;j<points+1;j++){
      if(dis[i][j]!=0)
      cout<<"("<<i<<","<<j<<")"<<dis[i][j]<<endl;
    }
  }
}
int main(){
  int i,j;
  scanf("%d %d",&points,&edges);
  for(i=1;i<points+1;i++){
    for(j=1;j<points+1;j++){
      dis[i][j]=INF;
    }
  }
  int point1,point2,length;
  for(i=0;i<edges;i++){
    scanf("%d %d %d",&point1,&point2,&length);
    dis[point1][point2]=length;
    dis[point2][point1]=length;
  }
  Floyd();
  show();
}