dijkstra——Job Hunt S(负环)

原文链接：https://www.luogu.com.cn/problem/P1938

AC代码：

#include<iostream>
#include<string.h>
#include<vector>
#include<queue>
#include<algorithm>
using namespace std;
int D,C,P,F,S;
int mapp[305][305],lowc[305],sum[305],visit[305],flag=0,ans;
typedef struct node{
	int id,w;
	bool operator <(const node &a)const{
		return a.w>w;
	}
}node;
node nod,nodd;
priority_queue<node> que;
void dijkstra(){
	int i,j;
	nod.id=S;nod.w=D;
	lowc[S]=D;
	que.push(nod);
	while(!que.empty()){
		nod=que.top();que.pop();//cout<<nod.id<<" "<<nod.w<<endl;
		sum[nod.id]++;
		if(sum[nod.id]>C){//判断负环 
			cout<<"-1"<<endl;
			exit(0);
		}
		/*if(visit[nod.id]==1){
			continue;
		}
		visit[nod.id]=1;*/
		for(i=1;i<=C;i++){
			//cout<<nod.id<<" "<<i<<" "<<lowc[nod.id]<<" "<<mapp[nod.id][i]<<" "<<lowc[i]<<endl;
			if(mapp[nod.id][i]+lowc[nod.id]>lowc[i]){
				lowc[i]=mapp[nod.id][i]+lowc[nod.id];
				nodd.id=i;nodd.w=lowc[i];
				que.push(nodd);
			}
		}
	}
}
int main(){
	int i,j;
	for(i=0;i<305;i++){
		for(j=0;j<305;j++){
			mapp[i][j]=-1e8;
		}
		lowc[i]=-1e8;sum[i]=0;visit[i]=0;
	}
	cin>>D>>P>>C>>F>>S;
	for(i=0;i<P;i++){
		int x,y;
		cin>>x>>y;
		mapp[x][y]=D;
	}
	for(i=0;i<F;i++){
		int x,y,z;
		cin>>x>>y>>z;
		if(mapp[x][y]<D-z){
			mapp[x][y]=D-z;
		}
	}
	dijkstra();
	for(i=1;i<=C;i++){
		ans=max(ans,lowc[i]);
	}
	cout<<ans<<endl; 
	return 0;
}