P1807 最长路

SPFA变负权跑最短路即可(dij不行)

#include <bits/stdc++.h>
using namespace std;
typedef long long ll;
int n,m,s,bk[400005],head[400005],cnt;
ll x,y,z,inf=INT_MAX,dis[400005];
struct edge
{
	ll to,w,nxt;
}e[4000005];
void add(ll x,ll y,ll z)
{
	e[++cnt].to=y;e[cnt].w=z;e[cnt].nxt=head[x];head[x]=cnt;
}
void spfa()
{
	for(int i=1;i<=n;i++)
	dis[i]=i==s?0:inf;
	queue<int> q;
	q.push(s);
	while(q.size())
	{
		int jk=q.front();
		q.pop();
		bk[jk]=0;
		for(int i=head[jk];i;i=e[i].nxt)
		if(dis[e[i].to]>dis[jk]+e[i].w)
		{
			dis[e[i].to]=dis[jk]+e[i].w;
			if(!bk[e[i].to])
			q.push(e[i].to),bk[e[i].to]=1;
		}
	}
	printf("%lld",dis[n]==inf?-1:-dis[n]);
}
int main()
{
	scanf("%d%d",&n,&m);
	s=1;
	while(m--)
	{
		scanf("%lld%lld%lld",&x,&y,&z);
		add(x,y,-z);
	}
	spfa();
}