用C语言求地铁最短线路的思路

对于地铁最短线路问题，可以使用 Dijkstra 算法来解决。以下是实现思路：

1. 定义地铁线路的图结构，每个地铁站为图中的一个节点，每条地铁线路为图中的一条边，边的权重为相邻两个站点之间的距离或时间。
2. 定义一个数组 dist 存放起点到各个站点的最短距离，初始值为无穷大，起点的最短距离为 0。
3. 定义一个数组 visited，用于记录每个节点是否已被访问，初始值为 false。
4. 使用堆或优先队列来存储未访问的节点，每次取出距离起点最近的节点进行访问，并更新其相邻节点的最短距离。
5. 重复步骤 4，直到所有节点都被访问或者终点已被访问。

以下是一个简单的 C 语言实现：

#include <stdio.h>
#include <limits.h>

#define MAX_STATIONS 100
#define INF INT_MAX

typedef struct {
    int weight;
    int next;
} Edge;

Edge edges[MAX_STATIONS * MAX_STATIONS];
int head[MAX_STATIONS], edge_cnt;

int dist[MAX_STATIONS];
int visited[MAX_STATIONS];

void add_edge(int u, int v, int w) {
    edges[++edge_cnt].next = head[u];
    edges[edge_cnt].weight = w;
    head[u] = edge_cnt;
}

void dijkstra(int s, int n) {
    for (int i = 1; i <= n; i++) {
        dist[i] = INF;
        visited[i] = 0;
    }
    dist[s] = 0;
    for (int i = 1; i <= n; i++) {
        int u = -1;
        for (int j = 1; j <= n; j++) {
            if (!visited[j] && (u == -1 || dist[j] < dist[u])) {
                u = j;
            }
        }
        visited[u] = 1;
        for (int j = head[u]; j != 0; j = edges[j].next) {
            int v = edges[j].next;
            if (dist[u] + edges[j].weight < dist[v]) {
                dist[v] = dist[u] + edges[j].weight;
            }
        }
    }
}

int main() {
    // 构建地铁线路图
    int n, m;
    scanf("%d %d", &n, &m);
    for (int i = 1; i <= m; i++) {
        int u, v, w;
        scanf("%d %d %d", &u, &v, &w);
        add_edge(u, v, w);
        add_edge(v, u, w);
    }
    // 使用 dijkstra 算法求最短路径
    int s, t;
    scanf("%d %d", &s, &t);
    dijkstra(s, n);
    printf("%d\n", dist[t]);
    return 0;
}

其中，n 表示地铁站点数，m 表示地铁线路数，u，v，w 分别表示地铁线路的起点、终点和距离/时间。最后输入起点 s 和终点 t，输出最短路径的长度。