Floyd算法

/*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;}