c语言实现
时间: 2023-07-13 19:19:11 浏览: 47
下面是使用 Dijkstra 算法实现的 C 语言代码:
```c
#include <stdio.h>
#include <limits.h>
#define MAX_N 1000
int n; // 出租站数量
int r[MAX_N][MAX_N]; // 租金矩阵
int dist[MAX_N]; // 从出租站1到每个出租站的最短距离
int visited[MAX_N]; // 每个出租站是否已经被访问过
// 优先队列数据结构
typedef struct {
int v; // 出租站编号
int d; // 到出租站1的距离
} node;
typedef struct {
node data[MAX_N];
int size;
} heap;
void init_heap(heap *h) {
h->size = 0;
}
void push(heap *h, node x) {
int i = h->size++;
while (i > 0) {
int p = (i - 1) / 2;
if (h->data[p].d <= x.d) break;
h->data[i] = h->data[p];
i = p;
}
h->data[i] = x;
}
node pop(heap *h) {
node ret = h->data[0];
node x = h->data[--h->size];
int i = 0;
while (i * 2 + 1 < h->size) {
int a = i * 2 + 1, b = i * 2 + 2;
if (b < h->size && h->data[b].d < h->data[a].d) a = b;
if (h->data[a].d >= x.d) break;
h->data[i] = h->data[a];
i = a;
}
h->data[i] = x;
return ret;
}
int dijkstra(int s, int t) {
for (int i = 1; i <= n; i++) {
dist[i] = INT_MAX;
visited[i] = 0;
}
dist[s] = 0;
visited[s] = 1;
heap h;
init_heap(&h);
push(&h, (node){s, 0});
while (h.size) {
node u = pop(&h);
visited[u.v] = 1;
if (u.v == t) return dist[t];
for (int i = 1; i <= n; i++) {
if (visited[i]) continue;
int d = dist[u.v] + r[u.v][i];
if (d < dist[i]) {
dist[i] = d;
push(&h, (node){i, d});
}
}
}
return -1; // 无法到达
}
int main() {
scanf("%d", &n);
for (int i = 1; i < n; i++) {
for (int j = i + 1; j <= n; j++) {
scanf("%d", &r[i][j]);
r[j][i] = r[i][j]; // 由于 r(i,j) = r(j,i),因此可以将 r(j,i) 的值设置为 r(i,j)
}
}
int ans = dijkstra(1, n);
printf("%d\n", ans);
return 0;
}
```
注意:该代码使用了优先队列实现堆,因此需要实现 push 和 pop 操作。
相关推荐
![zip](https://img-home.csdnimg.cn/images/20210720083736.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)
![](https://csdnimg.cn/download_wenku/file_type_ask_c1.png)