C++解答

//ALGORIHTM::DC
//AUTHOR::STDAFX

#define MAXE 50000UL
#define MAXN 2000UL
#define INF 100000000L

#include <cstdio>
#include <cstring>

using namespace std;

bool SPFA();

struct Edge{
	int v,nx,w;
};

struct stack{
	int head,data[MAXE];
	inline int top(){
		return data[head];
	}
	inline bool empty(){
		return head==0;
	}
	inline void pop(){
		head--;
		return;
	}
	inline void push(int temp){
		data[++head]=temp;
		return;
	}
};

Edge edge[MAXE];

int n,ml,md,indgr[MAXN],headlist[MAXN],a,b,k,ec,dx[MAXN];

bool ex[MAXN];

stack sta;

int main(){
	scanf("%d%d%d",&n,&ml,&md);
	for(int i=1;i<=ml;i++){
		//a->b w=k;
		scanf("%d%d%d",&a,&b,&k);
		edge[++ec].v=b;
		edge[ec].w=k;
		edge[ec].nx=headlist[a];
		headlist[a]=ec;
	}
	for(int i=1;i<=md;i++){
		//b->a w=-k
		scanf("%d%d%d",&a,&b,&k);
		edge[++ec].v=a;
		edge[ec].w=-k;
		edge[ec].nx=headlist[b];
		headlist[b]=ec;
	}
	for(int i=1;i<n;i++){
		//i+1->i
		edge[++ec].v=i;
		edge[ec].w=0;
		edge[ec].nx=headlist[i+1];
		headlist[i+1]=ec;
	}
	if(!SPFA()){
		printf("-1");
	}
	else if(dx[n]>INF){
		printf("-2");
	}
	else{
		printf("%d",dx[n]);
	}
	return 0;
}

bool SPFA(){
	memset(dx,50,sizeof(dx));dx[1]=0;
	sta.push(1);
	while(!sta.empty()){
		k=sta.top();sta.pop();ex[k]=0;
		for(int i=headlist[k];i!=0;i=edge[i].nx){
			if(dx[edge[i].v]>dx[k]+edge[i].w){
				dx[edge[i].v]=dx[k]+edge[i].w;
				if(!ex[edge[i].v]){
					indgr[edge[i].v]++;
					if(indgr[edge[i].v]>n){
						return false;
					}
					ex[edge[i].v]=1;
					sta.push(edge[i].v);
				}
			}
		}
	}
	return true;
}