记录编号	537785	评测结果	EEEEEEEEEE
题目名称	[WC 2010模拟] 奶牛排队	最终得分	0
用户昵称	ShallowDream雨梨	是否通过	未通过
代码语言	C++	运行时间	1.250 s
提交时间	2019-07-16 21:55:14	内存使用	14.13 MiB

#include<bits/stdc++.h>
using namespace std;
const int maxn=10005;
bool in[maxn];
struct road{int to,next,v;
}a[maxn*3];
int r[maxn],head[maxn],tot,dis[maxn];
int n,l,u,q,w,e;
void add(int x,int y,int z){tot++;
	a[tot].to=y;
	a[tot].v=z;	
	a[tot].next=head[x];
	head[x]=tot;}
	
void spfa(int x){
	dis[x]=0;
	queue<int> q;
	q.push(x);
	in[x]=1;
	while(!q.empty()){
	int qwq=q.front();q.pop();
		in[qwq]=0;
	for(int i=head[qwq];i;i=a[i].next){
			if(dis[a[i].to]>dis[qwq]+a[i].v){
			dis[a[i].to]=dis[qwq]+a[i].v;	
			if(in[a[i].to]==0){
				in[a[i].to]=1;
				r[a[i].to]++;
				q.push(a[i].to);
				if(r[a[i].to]>n+5){
				cout<<-1;return;}}}}}
		//if(dis[n]<0){cout<<-1;return;}	\
		if(dis[n]==99999999){cout<<-2;return;}	
		cout<<dis[n];return;
					}
int main(){
	ios::sync_with_stdio(false);
	//freopen("layout.in", "r", stdin);
   // freopen("layout.out", "w", stdout);
	
	for(int i=1;i<=maxn;i++)dis[i]=99999999;
	cin>>n>>l>>u;
	for(int i=1;i<=l;i++){
		cin>>q>>w>>e;
		add(q,w,e);}
	for(int i=1;i<=u;i++){
		cin>>q>>w>>e;
		add(w,q,-e);}
	for(int i=n;i>=2;i--)
	add(i,i-1,0);
	spfa(1);
	
 return 0;   
}