股票经纪人要在一群人n 个人的编号为 0~n-1中散布一个传言传言只在认识的人中间传递。题目中给出了人与人的认识关系以及传言在某两个认识的人中传递所需要的时间。编写程序求出以哪个人为起点可以在耗时最短的情况下让所有人收到消息。用c语言写

#include <stdio.h> #include <stdlib.h>

#define INF 0x7fffffff

int graph[1000][1000]; // 存储传言传递所需时间的邻接矩阵 int visited[1000]; // 标记每个人是否已被访问 int dist[1000]; // 存储从起点到每个人的最短时间 int n; // 人数

int dijkstra(int start) { // Dijkstra算法求最短时间 for (int i = 0; i < n; i++) { visited[i] = 0; dist[i] = INF; } dist[start] = 0; for (int i = 0; i < n; i++) { int min_dist = INF, u = -1; for (int j = 0; j < n; j++) { if (!visited[j] && dist[j] < min_dist) { min_dist = dist[j]; u = j; } } if (u == -1) break; visited[u] = 1; for (int v = 0; v < n; v++) { if (!visited[v] && graph[u][v] != INF && dist[u] + graph[u][v] < dist[v]) { dist[v] = dist[u] + graph[u][v]; } } } int max_dist = 0; for (int i = 0; i < n; i++) { if (dist[i] == INF) return INF; // 有人无法接收到传言 if (dist[i] > max_dist) max_dist = dist[i]; } return max_dist; }

int main() { scanf("%d", &n); for (int i = 0; i < n; i++) { for (int j = 0; j < n; j++) { graph[i][j] = INF; } } int m; scanf("%d", &m); for (int i = 0; i < m; i++) { int u, v, t; scanf("%d %d %d", &u, &v, &t); graph[u][v] = graph[v][u] = t; // 无向图 } int min_time = INF, start; for (int i = 0; i < n; i++) { int time = dijkstra(i); if (time < min_time) { min_time = time; start = i; } } printf("%d\n", start); return 0;