用Java解决股票经纪人要在一群人(n 个人的编号为0~n-1)中散布一个传言,传言只在认识的人中间传递。题目中给出了人与人的认识关系以及传言在某两个认识的人中传递所需要的时间。编写程序求出以哪个人为起点可以在耗时最短的情况下让所有人收到消息。
时间: 2023-12-03 15:42:21 浏览: 137
这个问题可以使用 Dijkstra 算法来解决。我们可以把每个人看作图中的一个节点,每个认识关系看作一条边,边的权重就是传递传言所需要的时间。然后我们从每个节点开始运行 Dijkstra 算法,最后取所有起点中最小的路径长度作为答案。
下面是 Java 代码实现:
```java
import java.util.*;
public class Rumor {
static class Edge {
int to, weight;
Edge(int to, int weight) {
this.to = to;
this.weight = weight;
}
}
public static void main(String[] args) {
Scanner scanner = new Scanner(System.in);
int n = scanner.nextInt(); // 人数
int m = scanner.nextInt(); // 认识关系数
List<Edge>[] graph = new List[n];
for (int i = 0; i < n; i++) {
graph[i] = new ArrayList<>();
}
for (int i = 0; i < m; i++) {
int a = scanner.nextInt();
int b = scanner.nextInt();
int t = scanner.nextInt();
graph[a].add(new Edge(b, t));
graph[b].add(new Edge(a, t));
}
int ans = Integer.MAX_VALUE;
for (int i = 0; i < n; i++) {
int[] dist = dijkstra(graph, i);
int maxDist = 0;
for (int j = 0; j < n; j++) {
if (dist[j] == Integer.MAX_VALUE) {
maxDist = Integer.MAX_VALUE;
break;
}
maxDist = Math.max(maxDist, dist[j]);
}
ans = Math.min(ans, maxDist);
}
System.out.println(ans);
}
static int[] dijkstra(List<Edge>[] graph, int start) {
int n = graph.length;
int[] dist = new int[n];
Arrays.fill(dist, Integer.MAX_VALUE);
dist[start] = 0;
PriorityQueue<Integer> pq = new PriorityQueue<>((a, b) -> dist[a] - dist[b]);
pq.offer(start);
while (!pq.isEmpty()) {
int u = pq.poll();
if (dist[u] == Integer.MAX_VALUE) {
break;
}
for (Edge e : graph[u]) {
int v = e.to;
int newDist = dist[u] + e.weight;
if (newDist < dist[v]) {
dist[v] = newDist;
pq.offer(v);
}
}
}
return dist;
}
}
```
时间复杂度为 O(nmlogn),其中 n 是人数,m 是认识关系数。实际运行时间会受到具体数据的影响。
阅读全文