题解 | #【模板】单源最短路1#

#include <stdio.h>
#include <stdlib.h>
#include <string.h>

#define MAX_NODES 5009

// 定义邻接表节点
typedef struct Node {
    int vertex;
    struct Node* next;
} Node;

// 定义邻接表、访问数组和距离数组
Node* adj[MAX_NODES];
int visited[MAX_NODES], dist[MAX_NODES], queue[MAX_NODES];

// 广度优先搜索（BFS）函数
int bfs(int n) {
    int front = 0, rear = 0;
    // 初始化队列,并从1号点开始
    queue[rear++] = 1;
    visited[1] = 1; // 标记1号点为已访问
    dist[1] = 0; // 1号点的距离为0

    // 执行BFS
    while (front < rear) {
        int u = queue[front++]; // 取出队列的首元素
        // 遍历u的所有邻接点
        Node* curr = adj[u];
        while (curr != NULL) {
            int v = curr->vertex;
            // 如果v没有被访问过
            if (!visited[v]) {
                // 标记v为已访问
                visited[v] = 1;
                // 更新v的距离
                dist[v] = dist[u] + 1;
                // 将v加入队列
                queue[rear++] = v;
                // 如果v是n号点,返回最短距离
                if (v == n) {
                    return dist[v];
                }
            }
            curr = curr->next;
        }
    }
    // 如果没有找到从1号点到n号点的路径,返回-1
    return -1;
}

int main() {
    int n, m, u, v;
    // 读取节点数和边数
    scanf("%d %d", &n, &m);
    // 初始化邻接表
    for (int i = 1; i <= n; i++) {
        adj[i] = NULL;
    }
    // 读取m条边,并更新邻接表
    while (m--) {
        scanf("%d %d", &u, &v);
        // 创建新节点并添加到u的邻接表中
        Node* newNode = (Node*)malloc(sizeof(Node));
        newNode->vertex = v;
        newNode->next = adj[u];
        adj[u] = newNode;
        // 创建新节点并添加到v的邻接表中(无向图)
        newNode = (Node*)malloc(sizeof(Node));
        newNode->vertex = u;
        newNode->next = adj[v];
        adj[v] = newNode;
    }
    // 调用BFS函数查找从1号点到n号点的最短距离
    printf("%d\n", bfs(n));
    return 0;
}