为庆祝五一,文达李谭谭同学也准备去安庆天柱山旅游,并且列出了每两个景点之间的距离和门票价格。请你设计一个程序来帮助李谭谭同学找到最佳的旅游路线,并计算出旅行的总里程和总费用。用c语言编程解决
时间: 2024-02-22 09:00:58 浏览: 49
好的,我可以为你提供一个基于 Dijkstra 算法的解决方案来解决这个问题。以下是 C 语言的代码实现:
```c
#include <stdio.h>
#include <stdlib.h>
#include <string.h>
#include <limits.h>
#define MAX_VERTICES 1000
#define INF INT_MAX
typedef struct {
int cost;
int distance;
} Edge;
typedef struct {
int vertex;
Edge edges[MAX_VERTICES];
int edge_count;
} Vertex;
typedef struct {
Vertex vertices[MAX_VERTICES];
int vertex_count;
} Graph;
int find_nearest_vertex(int distances[], int visited[], int vertices_count) {
int min_distance = INF;
int nearest_vertex = -1;
for (int i = 0; i < vertices_count; i++) {
if (visited[i] == 0 && distances[i] < min_distance) {
min_distance = distances[i];
nearest_vertex = i;
}
}
return nearest_vertex;
}
void dijkstra(Graph *graph, int start_vertex, int distances[], int fees[], int vertices_count) {
int visited[MAX_VERTICES] = {0};
for (int i = 0; i < vertices_count; i++) {
distances[i] = INF;
fees[i] = 0;
}
distances[start_vertex] = 0;
for (int i = 0; i < vertices_count; i++) {
int current_vertex = find_nearest_vertex(distances, visited, vertices_count);
visited[current_vertex] = 1;
Vertex *vertex = &graph->vertices[current_vertex];
for (int j = 0; j < vertex->edge_count; j++) {
int neighbor_vertex = vertex->edges[j].distance;
int cost = vertex->edges[j].cost;
if (distances[current_vertex] + cost < distances[neighbor_vertex]) {
distances[neighbor_vertex] = distances[current_vertex] + cost;
fees[neighbor_vertex] = fees[current_vertex] + cost;
}
}
}
}
int main() {
Graph graph;
int distances[MAX_VERTICES];
int fees[MAX_VERTICES];
int vertices_count, edges_count, start_vertex, end_vertex;
// 读入顶点数和边数
scanf("%d %d", &vertices_count, &edges_count);
// 初始化图
graph.vertex_count = vertices_count;
for (int i = 0; i < vertices_count; i++) {
graph.vertices[i].vertex = i;
graph.vertices[i].edge_count = 0;
}
// 读入边并添加到图中
for (int i = 0; i < edges_count; i++) {
int vertex1, vertex2, cost, distance;
scanf("%d %d %d %d", &vertex1, &vertex2, &cost, &distance);
Vertex *v1 = &graph.vertices[vertex1];
v1->edges[v1->edge_count].distance = vertex2;
v1->edges[v1->edge_count].cost = cost;
v1->edge_count++;
Vertex *v2 = &graph.vertices[vertex2];
v2->edges[v2->edge_count].distance = vertex1;
v2->edges[v2->edge_count].cost = cost;
v2->edge_count++;
}
// 读入起点和终点
scanf("%d %d", &start_vertex, &end_vertex);
// 运行 Dijkstra 算法
dijkstra(&graph, start_vertex, distances, fees, vertices_count);
// 输出结果
printf("%d %d\n", distances[end_vertex], fees[end_vertex]);
return 0;
}
```
这个程序可以读入顶点数和边数,然后读入每条边的起点、终点、距离和门票价格。程序可以计算出从起点到终点的最短距离和最小费用,并输出这两个结果。
需要注意的是,这个程序中的 Graph 结构体采用了邻接表的方式来存储图。每个顶点都包含一个数组,用来存储到其他顶点的边。每个边包含两个属性:cost 和 distance,分别表示门票价格和距离。在 dijkstra 函数中,我们使用了一个 visited 数组来记录哪些顶点已经访问过了,以避免重复访问。