大概思路就是从末尾状态递推到初始状态并记下最优路径

dfs(拓扑图求最短路径)

int path[N],cnt=0;

void dfs(int i,int j)
{
    if(!i) return ;
    for(int a=0;a<=j;a++)
    {
        if(f[i][j]==f[i-1][j-a]+w[i][a])
        {
            path[cnt++]=a;
            dfs(i-1,j-a);
            return ;//一定要有return，我的理解是可能会有多个状态满足，但我们只求最短路
        }
    }

}
for(int i=cnt-1,id=1;i>=0;i--,id++)
    {
        cout<<id<<" "<<path[i]<<endl;
    }

递推

    int j=m;
    for(int i=n;i>=1;i--)
    {
        for(int k=0;k<=j;k++)
        {
            if(f[i][j]==f[i-1][j-k]+w[i][k])
            {
                path[i]=k;
                j-=k;
                break;
            }
        }
    }

   for(int i=1;i<=n;i++) cout<<i<<" "<<path[i]<<endl;