最短路

https://www.luogu.com.cn/problem/B3647

都是基于松弛更新最短路的，即：dis[u][v]=min(dis[u][v], dis[u][k]+dis[k][v])，其中u是起点，v是终点，k是u->v路径中的一点。

记得考虑重边，自环的情况！！

Floyd

多源最短路，即求多个 u->v 的最短路，考虑dp转移即可。

O(n^3)，与n次dij要快速度差不多。

dp状态：dis[i][j]，表示从i点到j点的最短路

更新，正常这两个状态不好更新，引入一个中点k，其中k是i->j路径中的一点。

这样就容易更新了。

假设u是起点，v是终点，k是中点，那么：

dis[u][v]=min(dis[u][v], dis[u][k]+dis[k][v])

由于是dp，所以dp转移的时候要先枚举k。

#include <bits/stdc++.h>
using namespace std;
const int N=105;

int n, m, u1, v1, w1, dis[N][N];
void floyd()
{
	for (int k=1; k<=n; k++)
		for (int i=1; i<=n; i++)
			for (int j=1; j<=n; j++)
				dis[i][j]=min(dis[i][j], dis[i][k]+dis[k][j]); 
}
int main()
{
	memset(dis, 63, sizeof dis);
	
	scanf("%d%d", &n, &m);
	while (m--)
	{
		scanf("%d%d%d", &u1, &v1, &w1);
		dis[u1][v1]=min(dis[u1][v1], w1); //重边 
		dis[v1][u1]=min(dis[v1][u1], w1);
	}
	for (int i=1; i<=n; i++) dis[i][i]=0;
	
	floyd();
	
	for (int i=1; i<=n; i++)
	{
		for (int j=1; j<=n; j++) printf("%d ", dis[i][j]);
		printf("\n");
	}
	return 0;
}