牛妹的野菜

先把路径可行的转化成01矩阵的形式做一下预处理，方便后面
使用dp[]记录以这个点为终点的最多番薯数量
枚举所有两两相连的路径，更新dp，边更新边记录连接关系c[i]=j，表示j->i有最优的路径。
然后，逆流而上，找到头。输出~~
注意一个小坑是数组以0开始下标，输出和connectRoad都是1开始的记法呀

class Solution {
public:
    /**
     *
     * @param potatoNum int整型vector 依次表示序号为1,2,3..的番薯洞各有多少个番薯
     * @param connectRoad int整型vector<vector<>> 每个一维数组[x,y]表示从第x号番薯洞到第y号有路
     * @return string字符串
     */
    string digSum(vector<int>& potatoNum, vector<vector<int> >& connectRoad) {
        // write code here
        int n = potatoNum.size();
        vector<int>dp(n+1,0);
        dp[0] = 0;
        vector<int>c(n+1,0);
        vector<int>b(n+1,0);
        vector<vector<int> > x(n+1, vector<int>(n+1, 0));
        for (int i = 1; i <= n; i ++) x[0][i] = 1;
        for (int i = 0; i < connectRoad.size(); i ++) {
            x[connectRoad[i][0]][connectRoad[i][1]] = 1;
        }
        for (int i = 1; i <= n; i ++) {
            for (int j = i-1; j >= 0; j --) {
                if (x[j][i] == 1 && dp[i] < dp[j] + potatoNum[i-1]) {
                    c[i] = j;
                    dp[i] = dp[j] + potatoNum[i-1];
                }
            }
        }
        int kt = 0, mx = -999;
        for (int i = 1; i <= n; i ++) {
            if (mx < dp[i]) {
                mx = dp[i];
                kt = i;
            }
        }
        int p = 0;
        while (kt != 0) {
            b[++p] = kt;
            kt = c[kt];
        }
        string ans = "";
        string spl = "-";
        for (int i = p; i >= 1; i --) {
            ans += to_string(b[i]);
            if(i!=1) ans += spl;
        }
        return ans;
    }
};