设图中顶点表示村庄,有向边代表交通路线。若要建立一家医院,试问这家医院建在哪一个村庄使各村庄到医院总体上的交通代价最小,C语言实现
时间: 2023-08-12 11:06:28 浏览: 238
这是一个最短路径问题,可以使用Dijkstra算法来解决。以下是C语言实现代码,假设村庄总数为n,交通路线总数为m:
```c
#include <stdio.h>
#include <limits.h>
#define MAXN 1000 // 最大村庄数
#define MAXM 10000 // 最大交通路线数
int n, m; // 村庄数和交通路线数
int first[MAXN], nxt[MAXM], to[MAXM], w[MAXM]; // 邻接表存图
int dist[MAXN]; // 存储到各个村庄的最短距离
int vis[MAXN]; // 标记是否已经确定了最短路径
void add_edge(int u, int v, int c) {
static int cnt = 0;
nxt[++cnt] = first[u];
first[u] = cnt;
to[cnt] = v;
w[cnt] = c;
}
void dijkstra(int s) {
for (int i = 1; i <= n; i++) {
dist[i] = INT_MAX;
vis[i] = 0;
}
dist[s] = 0;
for (int i = 1; i <= n; i++) {
int u = 0;
for (int j = 1; j <= n; j++) {
if (!vis[j] && (u == 0 || dist[j] < dist[u])) {
u = j;
}
}
vis[u] = 1;
for (int j = first[u]; j; j = nxt[j]) {
int v = to[j];
if (!vis[v] && dist[u] + w[j] < dist[v]) {
dist[v] = dist[u] + w[j];
}
}
}
}
int main() {
scanf("%d%d", &n, &m);
for (int i = 1; i <= m; i++) {
int u, v, c;
scanf("%d%d%d", &u, &v, &c);
add_edge(u, v, c);
}
int ans = INT_MAX, ans_pos = -1;
for (int i = 1; i <= n; i++) {
dijkstra(i);
int sum = 0;
for (int j = 1; j <= n; j++) {
sum += dist[j];
}
if (sum < ans) {
ans = sum;
ans_pos = i;
}
}
printf("医院建在村庄%d,交通代价为%d\n", ans_pos, ans);
return 0;
}
```
代码思路:
1. 使用邻接表存储图。
2. 对于每个村庄,使用 Dijkstra 算法求出到其他村庄的最短距离。
3. 对于每个村庄,将到其他村庄的最短距离求和,找到交通代价最小的村庄。
4. 输出结果。
相关推荐
![application/x-rar](https://img-home.csdnimg.cn/images/20210720083606.png)
![cpp](https://img-home.csdnimg.cn/images/20210720083646.png)
![pdf](https://img-home.csdnimg.cn/images/20210720083512.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)
![](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)