C++图中顶点表示村庄,有向边代表交通路线.有向图采用邻接矩阵的形式存储; 输出医院地址,以及各村庄到医院的交通代价。
时间: 2024-02-12 17:05:55 浏览: 26
好的,根据您的问题,我可以为您提供以下代码实现:
```c++
#include <iostream>
#include <limits.h>
using namespace std;
const int MAXN = 100; // 最大顶点数
const int INF = INT_MAX; // 代表无穷大
int graph[MAXN][MAXN]; // 邻接矩阵存储图
int dist[MAXN]; // 存储各村庄到医院的最短路径
bool visited[MAXN]; // 存储各村庄是否已经被访问
int n; // 图的顶点数
// Dijkstra算法求解最短路径
void Dijkstra(int start) {
for (int i = 0; i < n; i++) {
dist[i] = graph[start][i]; // 初始化距离为邻接矩阵中的值
visited[i] = false; // 初始化所有村庄都未被访问
}
visited[start] = true; // 起点已经被访问
for (int i = 0; i < n; i++) {
int minDist = INF;
int u = start;
for (int j = 0; j < n; j++) {
if (!visited[j] && dist[j] < minDist) {
minDist = dist[j];
u = j;
}
}
visited[u] = true;
for (int v = 0; v < n; v++) {
if (!visited[v] && graph[u][v] != INF) {
if (dist[u] + graph[u][v] < dist[v]) {
dist[v] = dist[u] + graph[u][v];
}
}
}
}
}
int main() {
int hospital; // 医院地址
cout << "请输入医院地址(顶点编号从0开始):";
cin >> hospital;
cout << "请输入图的顶点数:";
cin >> n;
cout << "请输入邻接矩阵(用INF表示无穷大):" << endl;
for (int i = 0; i < n; i++) {
for (int j = 0; j < n; j++) {
cin >> graph[i][j];
}
}
Dijkstra(hospital);
cout << "医院地址为:" << hospital << endl;
for (int i = 0; i < n; i++) {
if (i != hospital) {
cout << "村庄" << i << "到医院的交通代价为:" << dist[i] << endl;
}
}
return 0;
}
```
该代码实现了Dijkstra算法求解最短路径,并且可以输出医院地址,以及各村庄到医院的交通代价。您只需要输入医院地址、图的顶点数以及邻接矩阵即可得到结果。