#include <stdio.h>#include <stdlib.h>struct ENode { int adjVex; int w; struct ENode* nextArc;};struct ENode** a; //邻接表int* cost; //cost[i]表示i节点到汇点的最短路径长度int n; //总节点数int m; //总边数int i; //循环变量void CreatGraph(); //构建邻接表void FMultiGraph(); //多段图的向前递推算法int main() { scanf("%d%d", &n, &m); a = (struct ENode**) malloc(n * sizeof(struct ENode*)); CreatGraph(); FMultiGraph(); printf("%d\n", cost[0]); free(cost); for (i = 0; i < n; i++) free(a[i]); free(a); return 0;}//构建邻接表void CreatGraph() { int u, v; int w; struct ENode* t; //临时变量 for (i = 0; i < n; i++) a[i] = NULL; for (i = 0; i < m; i++) { scanf("%d%d%d", &u, &v, &w); t = (struct ENode*) malloc(sizeof(struct ENode)); t->adjVex = v; t->nextArc = a[u]; t->w = w; a[u] = t; }}//多段图的向前递推算法void FMultiGraph() { cost = (int*) malloc(n * sizeof(int)); cost[n - 1] = 0; //汇点到汇点的最短路径长度为0 struct ENode* r; //临时变量 int min; for (i = n - 2; i >= 0; i--) { min = 0x7fffffff; for (r = a[i]; r; r = r->nextArc) { if (r->w + cost[r->adjVex] < min) min = r->w + cost[r->adjVex]; } cost[i] = min; }}加一串记录路径，可以在构建邻接表时再添加一个数组用于记录前驱节点，然后在向前递推算法中回溯路径输出路径的代码

可以在节点的结构体中添加一个前驱节点的指针，然后在构建邻接表时初始化该指针，记录每个节点的前驱节点。在向前递推算法中，除了记录最短路径长度之外，还需要记录每个节点的前驱节点，最后回溯路径输出即可。

修改后的代码如下：

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

struct ENode {
int adjVex;
int w;
struct ENode* nextArc;
};

struct Node {
struct ENode* firstArc;
struct Node* preNode; //前驱节点指针
};

struct ENode** a; //邻接表
struct Node* nodes; //节点数组
int* cost; //cost[i]表示i节点到汇点的最短路径长度
int n; //总节点数
int m; //总边数
int i; //循环变量

void CreatGraph(); //构建邻接表
void FMultiGraph(); //多段图的向前递推算法
void PrintPath(); //输出路径

int main() {
scanf("%d%d", &n, &m);
a = (struct ENode**) malloc(n * sizeof(struct ENode*));
nodes = (struct Node*) malloc(n * sizeof(struct Node)); //节点数组初始化
CreatGraph();
FMultiGraph();
printf("%d\n", cost[0]);
PrintPath(); //输出路径
free(cost);
for (i = 0; i < n; i++) {
struct ENode* p = a[i];
while (p) {
struct ENode* q = p->nextArc;
free(p);
p = q;
}
}
free(a);
free(nodes); //释放节点数组
return 0;
}

//构建邻接表
void CreatGraph() {
int u, v;
int w;
struct ENode* t; //临时变量
for (i = 0; i < n; i++) {
a[i] = NULL;
nodes[i].preNode = NULL; //前驱节点指针初始化
}
for (i = 0; i < m; i++) {
scanf("%d%d%d", &u, &v, &w);
t = (struct ENode*) malloc(sizeof(struct ENode));
t->adjVex = v;
t->nextArc = a[u];
t->w = w;
a[u] = t;
//记录前驱节点
if (nodes[v].preNode == NULL || nodes[v].preNode > &nodes[u]) {
nodes[v].preNode = &nodes[u];
}
}
}

//多段图的向前递推算法
void FMultiGraph() {
cost = (int*) malloc(n * sizeof(int));
cost[n - 1] = 0; //汇点到汇点的最短路径长度为0
struct ENode* r; //临时变量
int min;
for (i = n - 2; i >= 0; i--) {
min = 0x7fffffff;
for (r = a[i]; r; r = r->nextArc) {
if (r->w + cost[r->adjVex] < min) {
min = r->w + cost[r->adjVex];
//更新前驱节点指针
nodes[i].preNode = &nodes[r->adjVex];
}
}
cost[i] = min;
}
}

//输出路径
void PrintPath() {
struct Node* p = &nodes[0];
printf("0");
while (p->preNode != NULL) {
printf("->%d", (int)(p - nodes));
p = p->preNode;
}
printf("\n");
}