更新长度就是松弛定理

求具体路径的方法可以参考【动态规划】最长不下降序列

#include <bits/stdc++.h>
using namespace std;

const int N = 105,INF = 0x3f3f3f3f;
int a[N][N],f[N],n,c[N];

int main()
{
    cin >> n;
    for(int i=1;i<=n;i++)
        for(int j=1;j<=n;j++)
            cin >> a[i][j];
    
    memset(f,INF,sizeof f);
    f[n] = 0;
    for(int i=n-1;i>=1;i--)
    {
        for(int x=i+1;x<=n;x++)
        {
            if(a[i][x]>0 && f[x]!=INF && f[i]>a[i][x]+f[x])
            {
                f[i] = a[i][x]+f[x];
                c[i]=x;
            }
        }
    }
    cout << "minlong=" << f[1] << endl;
    int x=1;
    while(x!=0)
    {
        cout << x << " ";
        x = c[x];
    }
    return 0;
}