题解 | #【模板】单源最短路Ⅰ ‖ 无权图#

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

#define N 2000010
#define INF 0x3f3f3f3f

// 邻接表节点结构体
typedef struct Edge {
    int v;
    struct Edge* next;
} Edge;

// 用于存储每个顶点的邻接表表头指针
Edge* adjList[N];

// 记录从起点到每个顶点的最短路径长度
int dist[N];

// 结构体用于在队列中存储顶点及其距离信息（模拟优先队列中的元素）
typedef struct Node {
    int id;
    int dis;
} Node;

// 队列结构体
typedef struct Queue {
    Node* data;
    int front;
    int rear;
    int size;
} Queue;

// 队列初始化函数
void initQueue(Queue* q) {
    q->data = (Node*)malloc(sizeof(Node) * N);
    q->front = q->rear = 0;
    q->size = 0;
}

// 入队函数
void enqueue(Queue* q, Node node) {
    q->data[q->rear] = node;
    q->rear = (q->rear + 1) % N;
    q->size++;
}

// 出队函数
Node dequeue(Queue* q) {
    Node node = q->data[q->front];
    q->front = (q->front + 1) % N;
    q->size--;
    return node;
}

// 判断队列是否为空
int isEmpty(Queue* q) {
    return q->size == 0;
}

// Dijkstra算法实现函数
void dijkstra(int s, int n) {
    memset(dist, INF, sizeof(dist));
    dist[s] = 0;

    Queue q;
    initQueue(&q);
    Node start = {s, 0};
    enqueue(&q, start);

    while (!isEmpty(&q)) {
        Node now = dequeue(&q);
        int u = now.id;
        int d = now.dis;

        if (d > dist[u]) continue;

        Edge* p = adjList[u];
        while (p != NULL) {
            int v = p->v;
            if (dist[v] > dist[u] + 1) {
                dist[v] = dist[u] + 1;
                Node newNode = {v, dist[v]};
                enqueue(&q, newNode);
            }
            p = p->next;
        }
    }
}

// 释放邻接表内存函数（避免内存泄漏）
void freeAdjList() {
    for (int i = 0; i < N; i++) {
        Edge* p = adjList[i];
        while (p != NULL) {
            Edge* next = p->next;
            free(p);
            p = next;
        }
    }
}

int main() {
    int n, m, s;
    scanf("%d%d%d", &n, &m, &s);

    // 初始化邻接表表头指针为NULL
    memset(adjList, 0, sizeof(adjList));

    // 读入边的信息，构建邻接表
    for (int i = 0; i < m; i++) {
        int u, v;
        scanf("%d%d", &u, &v);
        Edge* newEdge = (Edge*)malloc(sizeof(Edge));
        newEdge->v = v;
        newEdge->next = adjList[u];
        adjList[u] = newEdge;
    }

    dijkstra(s, n);

    // 输出从起点到各个顶点的最短路径长度，若不存在路径则输出 -1
    for (int i = 1; i <= n; i++) {
        if (dist[i] == INF)
            printf("-1 ");
        else
            printf("%d ", dist[i]);
    }
    printf("\n");

    freeAdjList();

    return 0;
}