[最短路] aw1128. 信使(单源最短路建图+Floyd算法+最短路理解+模板题)

文章目录

• • 1. 题目来源
  • 2. 题目解析

1. 题目来源

链接：1128. 信使

相关链接：

• [图+最短路+模板] 五大最短路常用模板)

2. 题目解析

题目抽象：每个点接收到信的最短时间就是起点到该点的最短距离。 则问题转化为求起点到每个点最短距离的最大值，即可。

单源，无向图，无负权边，数据范围很小很小。最短路算法都能做。 在此写了最简单的 floyd 算法，注意先循环枚举 k。

单源最短路的 dist 数组存的就是源点到个点的最短路嗷，我们之前只是关注了源点到终点的最短路距离，其实 dist[k] 存的就是源点到 k 点的最短路距离。

所以，不管用哪种最短路算法求完，遍历一遍 dist[i] 数组，求个最大值出来就行了。

注意：

• 本题乍一看类似一个最小生成树，但是最小生成树是每个点到集合的最短距离，而不是每个点到 1 号点起点的最短距离。理解为最小生成树是错误的。
• 本题可能有重边，在使用 Floyd 时需要选择一个边权的最小值。
• 当边权为 1 时，可用 bfs。

时间复杂度： O ( n 3 ) O(n^3) O(n3)

空间复杂度： O ( n 2 ) O(n^2) O(n2)

Floyd ：

#include using namespace std;const int N = 105;int n, m;
int f[N][N];int main() {scanf("%d%d", &n, &m);memset(f, 0x3f, sizeof f);for (int i = 0; i < N; i ++ ) f[i][i] = 0;  // 这个是必要的，但是本题不加也可以过，主对角线必然为 0，不加不为 0while (m -- ) {int a, b, c;scanf("%d%d%d", &a, &b, &c);f[a][b] = f[b][a] = min(f[a][b], c);        // 防止有重边}// 先循环 kfor (int k = 1; k <= n; k ++ )for (int i = 1; i <= n; i ++ ) for (int j = 1; j <= n; j ++ ) f[i][j] = min(f[i][j], f[i][k] + f[k][j]);int res = 0;for (int i = 1; i <= n; i ++ ) res = max(res, f[1][i]);if (res == 0x3f3f3f3f) res = -1;printf("%d\n", res);return 0;
}

本文来自互联网用户投稿，文章观点仅代表作者本人，不代表本站立场，不承担相关法律责任。如若转载，请注明出处。 如若内容造成侵权/违法违规/事实不符，请点击【内容举报】进行投诉反馈！