有向无环图最长路径，自己运行可以，提交OJ为Wrong Anwser，向各位大佬求教！

Question

1.问题描述： 求有向无环图的最长路径，如有多条的，输出字典序最小值。

** 输入：**第一行两个整数 n、m。表示有 n 个节点，编号 1 ~ n；接下来有 m 行，每行三个整数 a、b、weight。

输出：若干空格分隔的整数，连成一条weight和最大的路线。若有多条，输出字典序最小的那条路线。

2.我的代码

#include <iostream>
using namespace std;

int DP(int i); 
void printPath(int i);
int TopoSort(int* arr);

int n = 100000;
int* dp = new int [n + 1];
int** G = new int* [n + 1];
int* choice = new int [n + 1]; //记录最长路径的后继顶点
int* od = new int [n + 1]; //out-degree

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

    for (int i = 0; i <= n; i ++)
        G[i] = new int[n];
    for (int i = 0; i <= n; i ++)
        for (int j = 0; j <= n; j ++)
            G[i][j] = -1;

    for (int i = 0; i <= n; i ++){
        od[i] = 0;
        dp[i] = 0;
        choice[i] = -1;
    } 

    int a, b, price;
    for (int i = 0; i < m; i ++){
        cin >> a >> b >> price;
        G[a][b] = price;
        od[a] ++;
    }

    int* tp = new int [n + 1]; 
    for (int i = n; i >= 1; i --)  //零出度拓扑排序
        tp[i] = TopoSort(od);

    for (int i = n; i >= 1; i --) //按照拓扑排序的逆序，依次计算节点的max-path 
        dp[tp[i]] = DP(tp[i]);

    int max_v = 0;
    int max_l = 0;
    for (int i = 1; i <= n; i ++)
        if(dp[i] > max_l){
            max_l = dp[i];
            max_v = i;
        }

    printPath(max_v);

    return 0;
}

int DP(int i){
    if (dp[i] > 0)
        return dp[i];

    for (int j = 1; j <= n; j ++){ //遍历i的所有出边 
        if(G[i][j] != -1){
            int temp = DP(j) + G[i][j];
            if (temp > dp[i]){
                dp[i] = temp;
                choice[i] = j;
            }
        }
    }

    return dp[i];
}

void printPath(int i){
    cout << i << ' '; 
    while(choice[i] != -1){
        i = choice[i];
        cout << i << ' ';
    }
}

int TopoSort(int* arr){
    for (int i = n; i >= 1; i --)
        if (arr[i] == 0){
            arr[i] = -1;

            for (int j = 1; j <= n; j ++)
                if (G[j][i] != -1)
                    od[j] --;
            return i;
        }
}

十分感激！！！
（时间和空间的一些限制不想管它惹……只想捞一下最基本的Wrong Answer。QAQ

Answer 1

https://blog.csdn.net/weixin_42326744/article/details/105039708