P1807

评测记录

#include <bits/stdc++.h>
#define int long long
#define f1(i,a,b) for(int i=a;i<=b;i++)
#define f2(i,a,b) for(int i=a;i>=b;i--)
#define ff(e,u) for(int e=h[u];e;e=nxt[e])
using namespace std;
const int N=1e5+5;
int read(){int x=0,f=1;char ch=getchar();while(!isdigit(ch)){if(ch=='-')f=-1;ch=getchar();}while(isdigit(ch)){x=x*10+(int)(ch-'0');ch=getchar();}return x*f;}

int h[N],to[N],nxt[N],w[N],in[N],cnt;

void add(int u,int v,int wi)
{
	to[++cnt]=v;
	nxt[cnt]=h[u];
	h[u]=cnt;
	w[cnt]=wi;
}
int n,m;
int ans=0;
int num[N];

void bfs()
{
	queue<int> q;
	int u,v;
	f1(i,2,n)
	{
		if(!in[i])
		{
			q.push(i);
		}
		num[i]=-0x7f7f7f7f7f7f7f;
	}
	num[1]=w[1];
	while(!q.empty())
	{
		u=q.front();q.pop();
		ff(e,u)
		{
			v=to[e];
			in[v]--;
			if(!in[v])q.push(v);
		}
	}
}

void topu()
{
	queue<int> q;
	int u,v;
	q.push(1);
	while(!q.empty())
	{
		u=q.front();q.pop();
		ff(e,u)
		{
			v=to[e];
			
			num[v]=max(num[v],num[u]+w[h[v]]);
			in[v]--;
			if(!in[v])q.push(v);
		}
	}
	if(num[n]==-0x7f7f7f7f7f7f7f){cout<<-1;return;}
	cout<<num[n];
}
bool flag[1505][1505];
signed main()
{
	n=read();m=read();
	if(m==0){cout<<-1;return 0;}
	for(int i=1;i<=m;i++)
	{
		int u=read();int v=read();int wi=read();
		if(flag[u][v])
		{
			w[h[u]]=max(w[h[u]],wi);
			continue;
		}
		flag[u][v]=1;
		add(u,v,wi);
		in[v]++;
	}
	bfs();
	topu();
	return 0;
}