拓扑排序

调不出来了……

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

vector<int> v[1505];
queue<int> q;
int inn[1505];
long long a[1505];
int l[1505][1505];

int main()
{
    int n,m;
    cin >> n >> m;
    memset(l,-127,sizeof(l));
    memset(a,-127,sizeof(a)); 
    for(int i=1;i<=m;i++)
    {
        int a,b,len;
        scanf("%d %d %d",&a,&b,&len);
        v[a].push_back(b);
        l[a][b] = len;
        inn[b]++;
    }
    
    for(int i=1;i<=n;i++)
        if(!inn[i])
        {
            q.push(i);
            a[i] = 0;
        }
        
    while(!q.empty())
    {
        int x = q.front();
        q.pop();
        for(int i=0; i<int(v[x].size());i++)
        {
            long long y = v[x][i];
            a[y] = max(a[y], a[x]+l[x][y]);
            inn[y]--;
            if(!inn[y])
                q.push(y);
        }
    }
    /*for(int i=1;i<=n;i++){
        for(int j=1;j<=n;j++)
            cout << l[i][j] << " ";
        cout << endl;}    
    for(int i=1;i<=n;i++)
            cout << a[i] << " ";*/
    cout << a[n];
    return 0;
}