用C语言写出对于给定一个的多段图，用动态规划法求起点到终点的最短路径

以下是用 C 语言实现对于给定一个多段图，用动态规划法求起点到终点的最短路径的代码：

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

#define MAX_N 100    // 最大顶点数
#define MAX_M 1000   // 最大边数

int n, m;   // 顶点数和边数
int w[MAX_N][MAX_N];   // 边的权值
int d[MAX_N][MAX_N];   // 最短路径长度
int p[MAX_N][MAX_N];   // 最短路径上的前驱顶点

// 多段图的动态规划算法
void multi_stage_graph()
{
    // 初始化
    for (int i = 1; i <= n; i++) {
        for (int j = 1; j <= n; j++) {
            if (i == j) {
                d[i][j] = 0;
            } else {
                d[i][j] = w[i][j];
            }
            p[i][j] = -1;
        }
    }

    // 状态转移
    for (int i = n - 1; i >= 1; i--) {
        for (int j = i + 1; j <= n; j++) {
            for (int k = i + 1; k < j; k++) {
                if (d[i][k] != INT_MAX && w[k][j] != INT_MAX) {
                    int temp = d[i][k] + w[k][j];
                    if (temp < d[i][j]) {
                        d[i][j] = temp;
                        p[i][j] = k;
                    }
                }
            }
        }
    }
}

// 输出最短路径
void print_path(int i, int j)
{
    if (i == j) {
        printf("%d ", i);
        return;
    }
    if (p[i][j] == -1) {
        printf("no path\n");
        return;
    }
    print_path(i, p[i][j]);
    printf("%d ", j);
}

int main()
{
    // 读入输入数据
    scanf("%d %d", &n, &m);
    for (int i = 1; i <= n; i++) {
        for (int j = 1; j <= n; j++) {
            if (i != j) {
                w[i][j] = INT_MAX;
            } else {
                w[i][j] = 0;
            }
        }
    }
    for (int i = 1; i <= m; i++) {
        int u, v, weight;
        scanf("%d %d %d", &u, &v, &weight);
        w[u][v] = weight;
    }

    // 求解多段图的最短路径
    multi_stage_graph();

    // 输出结果
    printf("Shortest path length: %d\n", d[1][n]);
    printf("Shortest path: ");
    print_path(1, n);
    printf("\n");

    return 0;
}

在这里，我们使用邻接矩阵来存储多段图。多段图的动态规划算法由三个嵌套循环组成，时间复杂度为 O(n^3)，其中 n 表示顶点数。