bfs

${\purple{\Huge code:} }$

#include<bits/stdc++.h>
using namespace std;
vector<int>g[50000];
queue<int>q;vector<int>l[50000];
int n,m,in[50000],f[50000];const int NINF=-1e9;
void bfs(){
	for(int i=2;i<=n;i++){f[i]=NINF;if(!in[i])q.push(i);}
	while(!q.empty()){
		int x=q.front();q.pop();
		for(int i=0;i<g[x].size();i++){
			if(!(--in[g[x][i]]))q.push(g[x][i]);
		}
	}
	q.push(1);f[1]=0;
	while(!q.empty()){
		int x=q.front();q.pop();
		for(int i=0;i<g[x].size();i++){
			if(f[g[x][i]]<f[x]+l[x][i])
				f[g[x][i]]=f[x]+l[x][i];
			if(!--in[g[x][i]])q.push(g[x][i]);
		}
	}
}
int main(){
	cin>>n>>m;
	for(int i=1;i<=m;i++){
		int a,b,c;cin>>a>>b>>c;l[a].push_back(c);
		g[a].push_back(b);in[a]++;
	}
	bfs();if(f[n]==NINF)cout<<-1;else cout<<f[n];return 0;
}

评测记录