Dijkstra算法来解决,C语言实现大陆有n个结点,你现在激活了1个节点,一旦节点被激活,就可以在任何位置到该节点,且不好时间,否则,需要沿着道路从一个已激活的结点走到另一个未激活的节点,然后激活它,已知地图上有m条路,每条路需要w分钟才能走完,现在需要激活所有系欸但,请问需要多长时间?
时间: 2023-06-09 16:04:11 浏览: 64
该问题可以使用Dijkstra算法求解。简单地说,Dijkstra算法是一种解决单源最短路径问题的贪心算法。在本题中,我们可以将已激活的结点作为起点,未激活的结点作为终点,将每条路的权重视为路径长度。使用Dijkstra算法计算出所有未激活结点到已激活结点的最短路径长度,然后取最大值即可。这个最大值就是需要的时间。下面是一个基本的C语言实现:
```c
#define MAXN 100 // 最大结点数
#define INF 0x3f3f3f3f // 无穷大
int map[MAXN][MAXN]; // 存储边权
int dist[MAXN]; // 存储起点到各点的最短路长度
bool visited[MAXN]; // 记录结点是否访问过
int dijkstra(int n, int start) {
for (int i = 1; i <= n; i++) {
dist[i] = INF;
visited[i] = false;
}
dist[start] = 0;
for (int i = 1; i <= n; i++) {
int u = 0, min_dist = INF;
for (int j = 1; j <= n; j++) {
if (!visited[j] && dist[j] < min_dist) {
u = j;
min_dist = dist[j];
}
}
if (u == 0) break;
visited[u] = true;
for (int v = 1; v <= n; v++) {
if (!visited[v] && map[u][v] != INF) {
int new_dist = dist[u] + map[u][v];
if (new_dist < dist[v]) {
dist[v] = new_dist;
}
}
}
}
int max_dist = 0;
for (int i = 1; i <= n; i++) {
if (dist[i] == INF) return INF; // 如果有结点无法到达,返回无穷大
if (!visited[i] && dist[i] > max_dist) {
max_dist = dist[i];
}
}
return max_dist;
}
int main() {
int n, m;
scanf("%d%d", &n, &m);
for (int i = 1; i <= n; i++) {
for (int j = 1; j <= n; j++) {
map[i][j] = INF;
}
}
for (int i = 1; i <= m; i++) {
int u, v, w;
scanf("%d%d%d", &u, &v, &w);
map[u][v] = map[v][u] = w;
}
int start = 1;
int time = dijkstra(n, start);
printf("%d\n", time);
return 0;
}
```
相关推荐
![pages](https://img-home.csdnimg.cn/images/20210720083646.png)
![](https://csdnimg.cn/download_wenku/file_type_ask_c1.png)
![](https://csdnimg.cn/download_wenku/file_type_ask_c1.png)
![](https://csdnimg.cn/download_wenku/file_type_ask_c1.png)
![](https://csdnimg.cn/download_wenku/file_type_ask_c1.png)
![](https://csdnimg.cn/download_wenku/file_type_ask_c1.png)
![](https://csdnimg.cn/download_wenku/file_type_ask_c1.png)
![](https://csdnimg.cn/download_wenku/file_type_ask_c1.png)
![](https://csdnimg.cn/download_wenku/file_type_ask_c1.png)
![](https://csdnimg.cn/download_wenku/file_type_ask_c1.png)
![](https://csdnimg.cn/download_wenku/file_type_ask_c1.png)
![](https://csdnimg.cn/download_wenku/file_type_ask_c1.png)
![rar](https://img-home.csdnimg.cn/images/20210720083606.png)