编写完整的程序【实验题目】:给出5个城市之间的公路交通图,如图所示,顶点表示城市,边表示城市之间的公路,边上的权值表示城市之间公路的长度。 大同 346 北京 146 370 291 天津 277 513 314 太原 223 石家庄 编程实现下面内容: (1)输入城市信息和城市之间公路信息,建立图的邻接矩阵存储结构。 (2)为了使所有城市之间能够通信,将沿公路敷设光缆,编程给出合理的敷设方案,使光纤总耗费最小。 (用C或者C++实现均可)
时间: 2024-02-03 18:14:55 浏览: 63
以下是C++实现的程序:
```cpp
#include <iostream>
#include <cstring>
using namespace std;
const int INF = 0x3f3f3f3f; // 定义一个无穷大的值
int n, m; // n为城市数量,m为公路数量
int graph[101][101]; // 存储城市之间的公路信息
int dist[101]; // 存储最短路径
bool visited[101]; // 记录是否访问过
void Dijkstra(int start) {
memset(visited, false, sizeof(visited)); // 初始化visited数组
memset(dist, INF, sizeof(dist)); // 初始化dist数组
dist[start] = 0; // 起点到自身的距离为0
for (int i = 1; i <= n; i++) {
int u = -1;
int minDist = INF;
for (int j = 1; j <= n; j++) {
if (!visited[j] && dist[j] < minDist) {
u = j;
minDist = dist[j];
}
}
if (u == -1) return; // 所有点都访问过了,结束循环
visited[u] = true;
for (int v = 1; 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 main() {
cin >> n >> m;
// 初始化图的邻接矩阵
for (int i = 1; i <= n; i++) {
for (int j = 1; j <= n; j++) {
if (i == j) {
graph[i][j] = 0;
} else {
graph[i][j] = INF;
}
}
}
// 输入城市之间的公路信息
for (int i = 1; i <= m; i++) {
int u, v, w;
cin >> u >> v >> w;
graph[u][v] = graph[v][u] = w; // 无向图
}
Dijkstra(1); // 以1号城市为起点进行最短路径算法
int totalCost = 0;
for (int i = 1; i <= n; i++) {
totalCost += dist[i];
}
cout << "最小光缆敷设总长度为:" << totalCost << endl;
return 0;
}
```
该程序使用了Dijkstra算法求解最短路径,最终输出了最小光缆敷设总长度。
相关推荐
![docx](https://img-home.csdnimg.cn/images/20210720083331.png)
![zip](https://img-home.csdnimg.cn/images/20210720083736.png)
![py](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)
![](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)