先发的

#include<cstdio>
#include<iostream>
#include<algorithm>
#include<cstring>
#include<queue>
#define int long long
using namespace std;
const int N=5e3+5;
int n,m,k,head[N],cnt,nxt[N],to[N],g[N],dis[N],s[N];
bool vis[N],vs[N];
void add(int x,int y,int z)
{
	nxt[++cnt]=head[x];
	head[x]=cnt;
	to[cnt]=y;
	g[cnt]=z;
}
void bfs()
{
	memset(vs,0,sizeof vs);
	dis[1]=0;
	queue<int> q;//队列 
	q.push(1);
	while(!q.empty())//如果q不为空，即q中仍有数 
	{
		int u=q.front();q.pop();
		vs[u]=0;
      	for(int i=head[u];i;i=nxt[i])
		{
			int v=to[i];
			if(dis[v]<dis[u]+g[i]&&vis[v])//不与n联通就没必要松弛了
			{
				dis[v] = dis[u]+g[i];
				if(!vs[v]) q.push(v),s[v]++,vs[v] = 1;
				if(s[v]>n)//判环
				{
					cout << -1;
					exit(0);//直接结束程序 
				}
			}
		}
	}
}
void dfs(int x,int y)//判是否与n联通
{
	if(x==n)
	{
		vis[y] = 1;
		return;
	}
	for(int i = head[x];i;i = nxt[i])
		if(!vs[to[i]])
			vs[to[i]] = 1,dfs(to[i],y);
}
signed main()
{
	ios::sync_with_stdio(false);//加速cin,cout 
	cin.tie(0);
	cout.tie(0);
	cin >> n >> m >> k;
	memset(dis,128,sizeof dis);
	for(int i=1,x,y,z;i<=m;i++)
	{
		cin >> x >> y >> z;
		add(x,y,z-k);
	}
	for(int i=1;i<=n;i++)
	{
		memset(vs,0,sizeof vs);//清空vs数组，即把vs数组每一个都变为0 
		vs[i] = 1;
		dfs(i,i);
	}
	bfs();
	if(dis[n]<0)
		dis[n]=0;
	cout << dis[n];
	return 0;
}

后发的

#include<bits/stdc++.h>
#define int long long
using namespace std;
const int N = 5e3+5;
int n,m,k,head[N],cnt,nxt[N],to[N],g[N],dis[N],s[N];
bool vis[N],vs[N];
void add(int x,int y,int z)
{
	nxt[++cnt] = head[x];
	head[x] = cnt;
	to[cnt] = y;
	g[cnt] = z;
}
void bfs()
{
	memset(vs,0,sizeof vs);
	dis[1] = 0;
	queue<int> q;
	q.push(1);
	while(!q.empty())
	{
		int u = q.front();q.pop();
		vs[u] = 0;
      	for(int i = head[u];i;i = nxt[i])
		{
			int v = to[i];
			if(dis[v]<dis[u]+g[i]&&vis[v])//不与n联通就没必要松弛了
			{
				dis[v] = dis[u]+g[i];
				if(!vs[v]) q.push(v),s[v]++,vs[v] = 1;
				if(s[v]>n)//判环
				{
					cout<<-1;
					exit(0);
				}
			}
		}
	}
}
void dfs(int x,int y)
{
	if(x==n)
	{
		vis[y] = 1;
		return;
	}
	for(int i = head[x];i;i = nxt[i])
		if(!vs[to[i]])
			vs[to[i]] = 1,dfs(to[i],y);
}//判是否与n联通
signed main()
{
	cin>>n>>m>>k;
	memset(dis,128,sizeof dis);
	for(int i = 1,x,y,z;i<=m;i++)
		cin>>x>>y>>z,add(x,y,z-k);
	for(int i = 1;i<=n;i++)
	{
		memset(vs,0,sizeof vs);
		vs[i] = 1;
		dfs(i,i);
	}
	bfs();
	if(dis[n]<0) dis[n] = 0;
	cout<<dis[n];
	return 0;
}

@wangyihao0411

@StarLbright40 @迟暮天复明 @Starrykiller