/*Floyd算法（用于解決全源最短路問題）流程如下：枚舉頂點k∈[1,n]	以頂點k作為中介點，枚舉所有頂點對i和j（i∈[1,n],j∈[1,n]）		如果dis[i][k]+dis[k][j]<dis[i][j]成立			賦值dis[i][j] = dis[i][k] + dis[k][j]*///下面是Floyd算法應用的代碼#include<cstdio>#include<algorithm>using namespace std;const int INF = 1000000000;const int MAXV = 200;//MAXV為最大頂點數int n, m;//n為頂點數，m為邊數int dis[MAXV][MAXV];//dis[i][j]表示頂點i和頂點j的最短距離void Floyd(){	for (int k = 0; k < n; k++)	{		for (int i = 0; i < n; i++)		{			for (int j = 0; j < n; j++)			{				if (dis[i][k] != INF&&dis[k][j] != INF					&&dis[i][k] + dis[k][j] < dis[i][j])					dis[i][j] = dis[i][k] + dis[k][j];//找到更短的路徑			}		}	}}int main(){	int u, v, w;	fill(dis[0], dis[0] + MAXV*MAXV, INF);//dis數組賦初值	scanf("%d%d", &n, &m);//頂點數n、邊數m	for (int i = 0; i < n; i++)	{		dis[i][i] = 0;//頂點i到頂點i的距離初始化為0	}	for (int i = 0; i < m; i++)	{		scanf("%d%d%d", &u, &v, &w);		dis[u][v] = w;//以有向圖為例進行輸入	}	Floyd();//Floyd算法入口	for (int i = 0; i < n; i++)//輸出dis數組	{		for (int j = 0; j < n; j++)		{			PRintf("%d ", dis[i][j]);		}		printf("/n");	}	return 0;}