多段图求最短路径动态规划C++代码

多段图最短路径问题可以使用动态规划算法来解决，以下是C++代码实现。

#include<iostream>
#include<cstring>
#include<cstdio>
using namespace std;
const int MAXN=1005,INF=0x3f3f3f3f;
int n,m,s,t,p;
int f[MAXN][MAXN]; //f[i][j] 表示从源点s到点i，在第j层的最短路长度
int g[MAXN][MAXN]; //g[i][j]表示第j层中到达点i的最短路长度

int main()
{
    scanf("%d%d",&n,&m);
    scanf("%d%d",&s,&t);
    memset(f,INF,sizeof(f));
    memset(g,INF,sizeof(g));
    for(int i=1;i<=n;++i) f[i][m]=0; //初始化最后一层
    for(int i=1;i<=m;++i) g[s][i]=0; //初始化第一层
    for(int i=1;i<=m;++i){
        int k;
        scanf("%d",&k); //输入第i层有多少个点
        for(int j=1;j<=k;++j){
            int x;
            scanf("%d",&x);
            scanf("%d",&p); //输入点x的出度
            for(int l=1;l<=p;++l){
                int y,w;
                scanf("%d%d",&y,&w);
                g[y][i]=min(g[y][i],f[x][i]+w); //更新
            }
        }
    }
    for(int i=m-1;i>=1;--i){
        for(int j=1;j<=n;++j){
            for(int k=1;k<=n;++k){
                if(g[k][i]==INF) continue;
                f[j][i]=min(f[j][i],f[k][i+1]+g[k][i]); //状态转移方程
            }
        }
    }
    printf("%d\n",f[t][1]);
    return 0;
}

其中，f[i][j] 表示从源点s到点i，在第j层的最短路长度；g[i][j]表示第j层中到达点i的最短路长度。在输入时，需要注意每个点的出度可能为0，需要特判。状态转移方程为：f[j][i]=min(f[j][i],f[k][i+1]+g[k][i])。最后输出f[t][1]即为从源点s到汇点t的最短路径长度。