Java解决股票经纪人KK想要在一群人(n个人的编号为0~n-1)中散布一个传言,传言只通过认识的人进行传递,在两个认识的人之间传递消息所需要的时间各有不同,在一群人中,KK想要找出以哪个人为起点开始传递这个传言,可以在耗时最短的情况下认所有人都收到消息。
时间: 2024-02-09 10:11:38 浏览: 132
关于java的传递方式问题
这个问题实际上就是一个最短路径问题,可以使用Dijkstra算法来解决。Dijkstra算法的基本思路是:从起点开始,依次找到到各个点的最短路径,直到找到终点为止。
以下是Java代码实现:
```java
public int spreadRumors(int n, int[][] edges, int[][] times) {
// 构建邻接矩阵
int[][] graph = new int[n][n];
for (int i = 0; i < n; i++) {
Arrays.fill(graph[i], Integer.MAX_VALUE);
graph[i][i] = 0;
}
for (int i = 0; i < edges.length; i++) {
int u = edges[i][0];
int v = edges[i][1];
int w = times[i][0];
graph[u][v] = w;
}
// 使用Dijkstra算法求解最短路径
int[] dist = new int[n];
boolean[] visited = new boolean[n];
Arrays.fill(dist, Integer.MAX_VALUE);
dist[0] = 0;
for (int i = 0; i < n; i++) {
int u = -1;
for (int j = 0; j < n; j++) {
if (!visited[j] && (u == -1 || dist[j] < dist[u])) {
u = j;
}
}
visited[u] = true;
for (int v = 0; v < n; v++) {
if (graph[u][v] != Integer.MAX_VALUE) {
dist[v] = Math.min(dist[v], dist[u] + graph[u][v]);
}
}
}
// 找到最大值
int max = 0;
for (int i = 0; i < n; i++) {
if (dist[i] == Integer.MAX_VALUE) {
return -1; // 无法到达的点,返回-1
}
max = Math.max(max, dist[i]);
}
return max;
}
```
其中,n表示人数,edges和times分别表示边和每条边的权值。首先构建邻接矩阵,然后使用Dijkstra算法求解从起点0到各个点的最短路径,最后找到最大值即可。
需要注意的是,如果存在无法到达的点,则返回-1。
阅读全文