【洛谷-图论】P1807 最长路

    //去除掉除了n以外的入度为0的点
    bool seenInd0[MAXN] = { false };        //已经去除的入度为0的顶点标记为true
    for (int idx = 2; idx <= n; idx++) {
        if (ind[idx] == 0&&seenInd0[idx]==false) {
            for (int j = 0; j < edges[idx].size(); j++) {
                int toP = edges[idx][j].first;      //到达的点
                ind[toP]--;
            }
            seenInd0[idx] = true;
            idx = 1;        //重新搜索,因为可能产生新的入度为0的点
        }
    }

#include<iostream>
#include<algorithm>
#include<vector>
#include<queue>

using namespace std;

const int MAXN = 1505;

vector<pair<int,int> > edges[MAXN];     //存点idx能到达点first，权值为second
int ind[MAXN],f[MAXN];                  //入度,到当前点的最大权值和
queue<int> que;

int main() {
    ios::sync_with_stdio(false);
    cin.tie(0);
    cout.tie(0);

    int n, m,tmp1,tmp2,tmp3;
    bool find = false;      //能到达n
    cin >> n >> m;

    for (int i = 1; i <= m; i++) {
        cin >> tmp1 >> tmp2 >> tmp3;
        edges[tmp1].push_back(make_pair(tmp2, tmp3));
        ind[tmp2]++;
    }
    //去除掉除了n以外的入度为0的点
    bool seenInd0[MAXN] = { false };
    for (int idx = 2; idx <= n; idx++) {
        if (ind[idx] == 0&&seenInd0[idx]==false) {
            for (int j = 0; j < edges[idx].size(); j++) {
                int toP = edges[idx][j].first;      //到达的点
                ind[toP]--;
            }
            seenInd0[idx] = true;
            idx = 1;        //重新搜索,因为可能产生新的入度为0的点
        }
    }
    que.push(1);
    while (que.empty() == false) {
        int u = que.front();
        que.pop();
        for (int i = 0; i < edges[u].size(); i++) {
            int v = edges[u][i].first,power = edges[u][i].second;
            f[v] = max(f[v], f[u]+power);
            ind[v]--;
            if(ind[v]==0)que.push(v);
            if (v == n)find = true;         
        }
    }
    cout << (find? f[n]:-1);

    return 0;
}