91 pts 求调玄2关

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

const int N=1505;
const int M=5e5+5;

int inline read(){
	int x=0,f=1;char ch=getchar();
	while(ch<'0'||ch>'9'){if(ch=='-')f=-1;ch=getchar();}
	while(ch>='0'&&ch<='9')x=x*10+(ch-'0'),ch=getchar();
	return x*f;
}

queue<int> q;
int a[N],vis[N],c[N];
int n,m;

struct Edge{
   int from,to,w;
}edge[M];

vector<Edge> v[M];
void topo_sort(){
    for(int i=1;i<=n;i++){
   		if(c[i]==0)
        q.push(i);
    }
    while(!q.empty()){
        int now=q.front();
        q.pop();
        for(int j=0;j<v[now].size();j++){
            c[v[now][j].to]--;
            if(vis[now]){
                if(a[v[now][j].to]<a[now]+v[now][j].w)
                a[v[now][j].to]=a[now]+v[now][j].w;
                vis[v[now][j].to]=1;
            }
            if(!c[v[now][j].to])
            q.push(v[now][j].to);
        }
    }
}
signed main(){
    cin>>n>>m;
    for(int i=0;i<m;i++){
    	cin>>edge[i].from>>edge[i].to>>edge[i].w;
        v[edge[i].from].push_back(edge[i]);
        c[edge[i].to]++;
    }
    a[n]=-1;
    vis[1]=1;
    topo_sort();
    cout<<a[n];
    return 0;
}