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