请设计void Dijkstra(Graph g, int s, int D[], int P[])函数。 该函数计算编号为s的顶点到所有顶点的最短路径长度及最短路径。 如果顶点不可达，则最短路径为INT_MAX。 数组D[]记录顶点s到对应顶点的最短距离(s到s的最短路径长度为0) 数组P[]记录顶点s到对应顶点的最短路径上的前驱(s到s的前驱为s)。 请注意，本题有预置代码，只需提交所要求的函数定义代码即可。邻接表，用c

以下是Dijkstra函数的代码实现，使用了邻接表来表示图：

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

#define MAX_VERTICES 1000

typedef struct _Edge {
    int to;
    int weight;
    struct _Edge* next;
} Edge;

typedef struct _Graph {
    Edge* adj[MAX_VERTICES];
    int num_vertices;
} Graph;

void addEdge(Graph* g, int from, int to, int weight) {
    Edge* e = (Edge*)malloc(sizeof(Edge));
    e->to = to;
    e->weight = weight;
    e->next = g->adj[from];
    g->adj[from] = e;
}

void Dijkstra(Graph g, int s, int D[], int P[]) {
    const int n = g.num_vertices;
    int visited[n];
    for (int i = 0; i < n; i++) {
        D[i] = INT_MAX;
        P[i] = -1;
        visited[i] = 0;
    }
    D[s] = 0;

    for (int i = 0; i < n - 1; i++) {
        int u = -1;
        for (int j = 0; j < n; j++) {
            if (!visited[j] && (u == -1 || D[j] < D[u])) {
                u = j;
            }
        }

        visited[u] = 1;
        for (Edge* e = g.adj[u]; e != NULL; e = e->next) {
            int v = e->to;
            if (!visited[v] && D[u] + e->weight < D[v]) {
                D[v] = D[u] + e->weight;
                P[v] = u;
            }
        }
    }
}

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

    Graph g;
    g.num_vertices = n;
    for (int i = 0; i < n; i++) {
        g.adj[i] = NULL;
    }

    for (int i = 0; i < m; i++) {
        int from, to, weight;
        scanf("%d%d%d", &from, &to, &weight);
        addEdge(&g, from, to, weight);
    }

    int D[MAX_VERTICES], P[MAX_VERTICES];
    Dijkstra(g, s, D, P);

    for (int i = 0; i < n; i++) {
        if (D[i] == INT_MAX) {
            printf("INT_MAX\n");
        } else {
            printf("%d\n", D[i]);
        }
    }

    return 0;
}

在该函数实现中，我们首先定义了邻接表数据结构，然后通过addEdge函数来添加边。Dijkstra函数使用了类似于邻接矩阵的实现方式，但是针对每个顶点只存储了邻接表中的链表头指针，而不是一个完整的链表。在每次循环中，我们从未访问过的顶点中选取距离起点最近的顶点，将该顶点标记为已访问，并更新起点到其它未访问顶点的最短距离及最短路径。最终，D数组中记录了起点s到各顶点的最短距离，P数组中记录了起点s到各顶点的最短路径上的前驱。如果顶点不可达，则最短路径为INT_MAX。