最短路
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; }
标签:图论,min,int,重温,短路,基础,更新,dp,dis From: https://www.cnblogs.com/didiao233/p/18502848