#include <bits/stdc++.h>
using namespace std;
const int N=10005;
int mon,n,m,t;
struct node{
	int y,w,next;
}a[N<<1];
int head[N],idx=0;
int vis[N],d[N],nums[N],sum[N];
void add(int x,int y,int k){
	a[++idx].y=y;a[idx].w=k; a[idx].next=head[x];
	head[x]=idx;
}
bool SPFA(int s){
	queue <int> q;
	memset(d,-0x3f,sizeof(d));
	memset(vis,0,sizeof(vis));
	memset(nums,0,sizeof(nums));
	d[s]=mon;
	vis[s]=1,nums[s]++;
	q.push(s);
	while(!q.empty()){
		int x=q.front();
		q.pop();
		vis[x]=0;
		for(int i=head[x];i;i=a[i].next){
			int y=a[i].y;
			if(d[y]<d[x]-a[i].w+mon){
				d[y]=d[x]-a[i].w+mon;
				if(!vis[y]){
					q.push(y);
					vis[y]=1;
					nums[y]++;
					if(nums[y]>n)
						return false;
				}
			}
		}
	}
	return true;
}

int main(){
	cin>>mon>>n>>m>>t;
	for(int i=1;i<=n;i++){
		int x,y;
		cin>>x>>y;
		add(x,y,0);
	}
	for(int i=1;i<=t;i++){
		int x,y,z;
		cin>>x>>y>>z;
		add(x,y,z);
	}
	int maxn=-100000;
	for(int i=1;i<=m;i++){
		if(!SPFA(i)){
			cout<<"orz"<<endl;
			return 0;
		}
		for(int j=1;j<=m;j++){
			maxn=max(maxn,d[j]);
		}
	}
	cout<<maxn<<endl;
}

这个题我们考试做的，胡乱写了个代码上去A了？ 这题是跑最长路，可最长路不是NP问题吗？看题解好像也是这个思路。。。

求大佬讲解！！！