就是u->v+t连了条权值为收益的边，跑遍最长路

#include<set>
#include<map>
#include<cmath>
#include<queue>
#include<stack>
#include<cstdio>
#include<cstring>
#include<iostream>
#include<algorithm>
#define RG register int
#define ll long long
#define inf (1<<30)
#define eps (1e-15)
#define maxn 1000005
#define maxm 1005
#define rep(i,a,b) for(RG i=a;i<=b;i++)
#define per(i,a,b) for(RG i=a;i>=b;i--)
using namespace std;
int n,m,p,cnt;
int head[maxn<<1],dis[maxn];
bool vis[maxn],fg[maxn];
struct E{
	int v,next,val;
}e[(maxn<<1)+maxm];
 
inline int read()
{
	int x=0,f=1;char c=getchar();
	while(c<'0'||c>'9'){if(c=='-')f=-1;c=getchar();}
	while(c>='0'&&c<='9'){x=x*10+c-'0';c=getchar();}
	return x*f;
}
 
inline void add(int u,int v,int val)
{
	e[++cnt].v=v,e[cnt].val=val,e[cnt].next=head[u],head[u]=cnt;
}
 
void SPFA()
{
	RG u,v;
	queue<int> que;
	que.push(0);
	while(!que.empty())
	{
		u=que.front(),que.pop();vis[u]=0;
		for(RG i=head[u];i;i=e[i].next)
		{
			v=e[i].v;
			if(dis[v]<=dis[u]+e[i].val)
			{
				dis[v]=dis[u]+e[i].val;
				if(!vis[v])	que.push(v),vis[v]=1;
			}
		}
	}
	printf("%d",dis[n+p]);
}
 
int main()
{
	RG hd=1,tl=0;
	n=read(),m=read(),p=read();
	int lim=n+p;
	RG u,v,val;rep(i,1,m)	u=read(),v=read(),val=read(),add(u,v+p,val),fg[u]=1,fg[v+p]=1;
	while(1)
	{
		while(!fg[hd]&&hd<lim)	hd++;
		add(tl,hd,0);
		if(hd>=lim)	break;
		tl=hd,hd++;
	}
	SPFA();
	return 0;
}