多段图的最短路径问题算法完整程序代码用C语言写

以下是使用C语言实现多段图的最短路径问题的算法代码：

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

#define INF 99999    // 无穷大

// 定义图的结构体
typedef struct {
    int u;          // 起点
    int v;          // 终点
    int w;          // 权值
} Edge;

int main() {
    int n, m;       // n为节点数，m为边数
    scanf("%d %d", &n, &m);

    Edge e[m+1];    // 存储边的数组
    for (int i = 1; i <= m; i++) {
        scanf("%d %d %d", &e[i].u, &e[i].v, &e[i].w);
    }

    int k;          // 分段数
    scanf("%d", &k);

    int d[n+1][k+1];    // 存储最短路径的二维数组
    // 初始化二维数组
    for (int i = 0; i <= n; i++) {
        for (int j = 0; j <= k; j++) {
            d[i][j] = INF;
        }
    }
    d[1][1] = 0;    // 起点到起点的距离为0

    // 计算最短路径
    for (int i = 1; i <= k; i++) {      // 分段循环
        for (int j = 1; j <= n; j++) {  // 节点循环
            for (int l = 1; l <= m; l++) {  // 边循环
                if (e[l].u == j && d[j][i-1] != INF) {
                    // 如果起点为j，且上一段到j的距离不为无穷大
                    int v = e[l].v;
                    int w = e[l].w;
                    if (d[v][i] > d[j][i-1] + w) {
                        // 如果到v的距离比到j再到v的距离长
                        d[v][i] = d[j][i-1] + w;  // 更新到v的最短路径
                    }
                }
            }
        }
    }

    printf("%d\n", d[n][k]);    // 输出起点到终点的最短路径

    return 0;
}