记录编号	117384	评测结果	AAAAAAAAAA
题目名称	[WC 2010模拟] 奶牛排队	最终得分	100
用户昵称	天一阁	是否通过	通过
代码语言	C++	运行时间	0.032 s
提交时间	2014-08-29 16:34:33	内存使用	1.23 MiB

#include <iostream>
#include <cstdio>
#include <cstring>
#include <climits>

using namespace std;

struct bian{
	int y,next,len;
}e[45001]={0};

int n,i,j,k,m,tot,x,y,z,st,en,o,tp,p,max,sum;
int f[1001]={0},g[1001]={0},ng[1001]={0},d[1001]={0},dist[1001]={0};
bool v[1001]={0};
int q[100001]={0};

void swap(int &x,int &y)
{
	int tp;
	tp=x;
	x=y;
	y=tp;
}

bool spfa(int x)
{
	bool res=false;
	int i,j,k,st,en,o,p;
	for(int i=1;i<=n;i++)
	{
		dist[i]=INT_MAX;
	}
	st=0, en=1, q[en]=x, v[x]=true;
	d[x]=1, dist[x]=0;
	while(st!=en)
	{
		if(st==100000) st=0;
		st++;
		o=g[q[st]];
		v[q[st]]=false;
		while(o!=0)
		{
			p=e[o].y;
			if(dist[p]>dist[q[st]]+e[o].len)
			{
				dist[p]=dist[q[st]]+e[o].len;
				if(!v[p])
				{
					q[++en]=p;
					v[p]=true;
					d[p]++;
					if(d[p]>n) return true;
				}
			}
			o=e[o].next;
		}
	}
}

void init()
{
	cin>>n>>m>>k;
	for(int i=1;i<=m;i++)
	{
		cin>>x>>y>>z;
		if(y<x) swap(x,y);
		tot++;
		e[tot].y=y;
		e[tot].len=z;
		e[tot].next=g[x];
		g[x]=tot;
	}
	for(int i=1;i<=k;i++)
	{
		cin>>x>>y>>z;
		tot++;
		e[tot].y=x;
		e[tot].len=-z;
		e[tot].next=g[y];
		g[y]=tot;
	}
	if(spfa(1))
	{
		cout<<-1<<endl;
		return;
	}
	if(dist[n]==INT_MAX)
	{
		cout<<-2<<endl;
		return;
	}
	cout<<dist[n]<<endl;
	return;
}

int main()
{
	freopen("layout.in","r",stdin);
	freopen("layout.out","w",stdout);
	
	init();
	
	return 0;
}