c++动态规划实现多段图最短路径问题，从顶点0到顶点9找到一条最短路径代码

以下是C++实现多段图最短路径问题的代码，通过动态规划算法实现：

#include <iostream>
#include <cstring>
using namespace std;

const int MAXN = 100;
const int INF = 1e9;

int n, m; // n为顶点数，m为边数
int g[MAXN][MAXN]; // 存储图的邻接矩阵
int d[MAXN][MAXN]; // 存储每个点到终点的最短距离
int p[MAXN][MAXN]; // 存储每个点到终点的最短路径上的前驱节点

int main()
{
    cin >> n >> m;

    // 初始化邻接矩阵
    memset(g, INF, sizeof(g));
    for(int i = 0; i < n; i++)
        g[i][i] = 0;

    // 读入边权
    for(int i = 0; i < m; i++)
    {
        int u, v, w;
        cin >> u >> v >> w;
        g[u][v] = w;
    }

    // 动态规划求解最短路径
    for(int i = n-2; i >= 0; i--)
    {
        for(int j = i+1; j < n; j++)
        {
            int minDist = INF, minIdx = -1;
            for(int k = i+1; k <= j; k++)
            {
                if(g[i][k] < INF && d[k][j] + g[i][k] < minDist)
                {
                    minDist = d[k][j] + g[i][k];
                    minIdx = k;
                }
            }
            d[i][j] = minDist;
            p[i][j] = minIdx;
        }
    }

    // 输出最短路径
    cout << "最短路径长度为：" << d[0][n-1] << endl;
    cout << "最短路径为：0 ";
    int cur = p[0][n-1];
    while(cur != n-1)
    {
        cout << cur << " ";
        cur = p[cur][n-1];
    }
    cout << n-1 << endl;

    return 0;
}

以上代码是求解从顶点0到顶点9的最短路径问题，其中g数组存储了图的邻接矩阵，d数组和p数组分别存储了每个点到终点的最短距离和最短路径上的前驱节点。通过动态规划算法，可以求解出从顶点0到顶点9的最短路径。