记录编号	168250	评测结果	AAAAAAAAAA
题目名称	[WC 2010模拟] 奶牛排队	最终得分	100
用户昵称	forever	是否通过	通过
代码语言	C++	运行时间	0.011 s
提交时间	2015-07-02 17:49:32	内存使用	0.57 MiB

#include<iostream>
#include<cstdlib>
#include<cstdio>
#include<cstring>
#include<queue>
using namespace std;
int dis[1005],head[1005],vis[1005],num[1005];
struct dd
{
	int zhong;
	int next;
	int juli;
}jie[21105];
int n,na,nb,nc,nd,ne;
bool spfa()
{   queue<int>po;
	for(int i=1;i<=n;++i)
	  dis[i]=9999999;
	dis[1]=0;
	vis[1]=1;
	++num[1];
	po.push(1);
	while(!po.empty())
	{
		int yu=po.front();
		po.pop();
		vis[yu]=0;
		for(int i=head[yu];i!=-1;i=jie[i].next)
		{
			int hj=jie[i].zhong;
			if(dis[hj]>dis[yu]+jie[i].juli)
			{
				dis[hj]=dis[yu]+jie[i].juli;
				if(!vis[hj])
				{
					po.push(hj);
					vis[hj]=1;
					++num[hj];
					if(num[hj]>n)
					{
						return false;
					}
				}
			}
		}
	}
	return true;
}
int main()
{   freopen("layout.in","r",stdin);
	freopen("layout.out","w",stdout);
	memset(head,-1,sizeof(head));
	scanf("%d%d%d",&n,&na,&nb);
	for(int i=1;i<=na;++i)
	{
		scanf("%d%d%d",&nc,&nd,&ne);
		jie[i].zhong=nd;
		jie[i].juli=ne;
		jie[i].next=head[nc];
		head[nc]=i;
	}
	for(int i=na+1;i<=nb+na;++i)
	{
		scanf("%d%d%d",&nc,&nd,&ne);
		jie[i].zhong=nc;
		jie[i].next=head[nd];
		jie[i].juli=-ne;
		head[nd]=i;
	}
	int tou=nb+na;
	for(int i=1;i<=n;++i)
	{
		jie[++tou].zhong=i;
		jie[tou].next=head[i+1];
		jie[tou].juli=0;
		head[i+1]=tou;
	}
	if(!spfa())
	  {
			printf("%d",-1);
			return 0;
	  }
	else
	 if(dis[n]>999999)
	 {
			printf("%d",-2);
			return 0;
	 }
	 else
	  printf("%d",dis[n]);
	 //system("pause");
}