用Java编写股票经纪人要在一群人中散布一个传言,传言只在认识的人中间传递。题目中给出了人与人的认识关系以及传言在某两个认识的人中传递所需的时间。编写程序求出以哪个人为起点可以在耗时最短的情况下让所有人收到消息。
时间: 2024-02-03 11:12:27 浏览: 90
这是一个经典的图论问题,可以使用 Dijkstra 算法来解决。我们可以把人与人之间的认识关系建立成一个有向图,人为节点,认识关系为边,边权为传递传言所需的时间。
接下来,我们以每个人为起点运行 Dijkstra 算法,求出从该点出发到达其他所有点的最短路径长度。最后,我们找到所有起点中,最短路径长度最大的那个起点,即为答案。
具体的 Java 代码实现如下:
```java
import java.util.*;
class Broker {
static int N = 1010;
static int INF = 0x3f3f3f3f;
static int n, m;
static int[][] g = new int[N][N];
static int[] dist = new int[N];
static boolean[] st = new boolean[N];
static int dijkstra(int start) {
Arrays.fill(dist, INF);
Arrays.fill(st, false);
dist[start] = 0;
for (int i = 0; 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;
for (int j = 1; j <= n; j++)
dist[j] = Math.min(dist[j], dist[t] + g[t][j]);
}
int res = 0;
for (int i = 1; i <= n; i++)
res = Math.max(res, dist[i]);
return res;
}
public static void main(String[] args) {
Scanner sc = new Scanner(System.in);
n = sc.nextInt();
m = sc.nextInt();
for (int i = 1; i <= n; i++)
Arrays.fill(g[i], INF);
while (m-- > 0) {
int a = sc.nextInt(), b = sc.nextInt(), c = sc.nextInt();
g[a][b] = g[b][a] = c;
}
int res = INF;
for (int i = 1; i <= n; i++)
res = Math.min(res, dijkstra(i));
System.out.println(res);
}
}
```
其中,`g` 数组用来表示图中的边权,`dist` 数组用来表示从起点到各个点的最短距离,`st` 数组用来表示某个点是否已经确定了最短路。在 `dijkstra` 函数中,我们以 `start` 为起点运行 Dijkstra 算法,求出最短距离,并返回最短路径中的最大值。
在 `main` 函数中,我们枚举每个点作为起点,求出以该点为起点时的最短路径长度,并取最小值作为答案。
时间复杂度为 $O(n^2)$,可以通过本题。
阅读全文