AcWing算法提高课-3.1.2信使

宣传一下算法提高课整理 <—

CSDN个人主页：更好的阅读体验 <—

题目传送门点这里

题目描述

战争时期，前线有 $n$ 个哨所，每个哨所可能会与其他若干个哨所之间有通信联系。

信使负责在哨所之间传递信息，当然，这是要花费一定时间的（以天为单位）。

指挥部设在第一个哨所。

当指挥部下达一个命令后，指挥部就派出若干个信使向与指挥部相连的哨所送信。

当一个哨所接到信后，这个哨所内的信使们也以同样的方式向其他哨所送信。信在一个哨所内停留的时间可以忽略不计。

直至所有 $n$ 个哨所全部接到命令后，送信才算成功。

因为准备充足，每个哨所内都安排了足够的信使（如果一个哨所与其他 k 个哨所有通信联系的话，这个哨所内至少会配备 $k$ 个信使）。

现在总指挥请你编一个程序，计算出完成整个送信过程最短需要多少时间。

输入格式

第 $1$ 行有两个整数 $n$ 和 $m$，中间用 $1$ 个空格隔开，分别表示有 $n$ 个哨所和 $m$ 条通信线路。

第 $2$ 至 $m+1$ 行：每行三个整数 $i、j、k$，中间用 $1$ 个空格隔开，表示第 $i$ 个和第 $j$ 个哨所之间存在 双向 通信线路，且这条线路要花费 $k$ 天。

输出格式

一个整数，表示完成整个送信过程的最短时间。

如果不是所有的哨所都能收到信，就输出-1。

数据范围

$1\le n\le 100,$
$1\le m\le 200,$
$1\le k\le 1000$

样例输入

4 4
1 2 4
2 3 7
2 4 1
3 4 6

样例输出

11

---

题目化简：

给定一个 $n$ 个点 $m$ 条边的无向图，求编号为1的点与其他点之间最短距离的最大值。

思路

这道题因为数据范围极小，为了节约代码长度，可以采用Floyd算法。

在求出任意两点间最短距离之后，遍历dist[1][i]，求出最大值。

Dijkstra算法与Floyd类似，代码部分也给出了朴素Dijkstra和堆优化Dijkstra的代码。

算法时间复杂度

如果采用Floyd算法，那么时间复杂度是$O(n^3)$；

朴素Dijkstra算法：$O(n^2)$, 但是代码较长；

堆优化Dijkstra算法：$O(m\log n)$，同样的代码较长

AC Code

$C++(Floyd)$

#include <iostream>
#include <cstring>
#include <algorithm>using namespace std;const int N = 110, inf = 1e9;int n, m;
int d[N][N];void init()
{for (int i = 1; i <= n; i ++ )for (int j = 1; j <= n; j ++ )if (i == j) d[i][j] = 0;else d[i][j] = inf;
}void floyd()
{for (int k = 1; k <= n; k ++ )for (int i = 1; i <= n; i ++ )for (int j = 1; j <= n; j ++ )d[i][j] = min(d[i][j], d[i][k] + d[k][j]);
}int main()
{cin >> n >> m;init();while (m -- ){int a, b, c;cin >> a >> b >> c;d[a][b] = min(d[a][b], c);d[b][a] = min(d[b][a], c);}floyd();int res = 0;for (int i = 2; i <= n; i ++ )res = max(res, d[1][i]);if (res == inf) puts("-1");else printf("%d\n", res);return 0;
}

$C++(朴素Dijkstra)$

#include <iostream>
#include <cstring>
#include <algorithm>using namespace std;const int N = 110;int n, m;
int g[N][N];
int dist[N];
bool st[N];int dijkstra()
{int res = 0;memset(dist, 0x3f, sizeof dist);dist[1] = 0;for (int i = 1; i <= n; i ++ ){int t = -1;for (int j = 1; j <= n; j ++ )if (!st[j] &&(t == -1 || dist[t] > dist[j]))t = j;st[t] = true;res = max(res, dist[t]);for (int j = 1; j <= n; j ++ )dist[j] = min(dist[j], dist[t] + g[t][j]);}return res == 0x3f3f3f3f ? -1 : res;
}
int main()
{memset(g, 0x3f, sizeof g);scanf("%d%d", &n, &m);while (m -- ){int a, b, c;scanf("%d%d%d", &a, &b, &c);g[a][b] = g[b][a] = min(g[a][b], c);}cout << dijkstra() << endl;return 0;
}

$C++(堆优化Dijkstra)$

#include <iostream>
#include <cstring>
#include <algorithm>
#include <queue>#define x first
#define y secondusing namespace std;typedef pair<int, int> PII;const int N = 110, M = N << 2;int n, m;
int h[N], e[M], w[M], ne[M], idx;
int dist[N];
bool st[N];void add(int a, int b, int c)
{e[idx] = b, w[idx] = c, ne[idx] = h[a], h[a] = idx ++ ;
}
int dijkstra()
{int res = 0, cnt = 0;memset(dist, 0x3f, sizeof dist);dist[1] = 0;priority_queue<PII, vector<PII>, greater<>> heap;heap.push({0, 1});while (!heap.empty()){PII u = heap.top();heap.pop();if (st[u.y]) continue;st[u.y] = true;res = max(res, u.x);cnt ++ ;for (int i = h[u.y]; ~i; i = ne[i]){int j = e[i];if (dist[j] > dist[u.y] + w[i]){dist[j] = dist[u.y] + w[i];heap.push({dist[j], j});}}}return cnt == n ? res : -1;
}
int main()
{memset(h, -1, sizeof h);scanf("%d%d", &n, &m);while (m -- ){int a, b, c;scanf("%d%d%d", &a, &b, &c);add(a, b, c), add(b, a, c);}cout << dijkstra() << endl;return 0;
}

最后，如果觉得对您有帮助的话，点个赞再走吧！