记录编号	27360	评测结果	AAAAAAAAAAA
题目名称	[USACO Nov09] 找工作	最终得分	100
用户昵称	belong.zmx	是否通过	通过
代码语言	C++	运行时间	0.006 s
提交时间	2011-09-17 16:20:19	内存使用	8.84 MiB

#include <iostream>
#include <cstdlib>
#include <cstdio>

using namespace std;

const int oo=99999999;

int i,j,dd,pp,ff,cc,ss,x,y,z,ans;
int way[221][221];
int q[2200001],f[221];
bool t[221],flag;

void spfa()
{
	int head,tail,i;
	head=1;tail=1;
	q[head]=ss;t[ss]=true;f[ss]=-dd;
	do
	{
		for (i=1;i<=cc;i++)
		{
			if (way[q[head]][i]<oo)
			{
				if (f[i]>f[q[head]]+way[q[head]][i])
				{
					f[i]=f[q[head]]+way[q[head]][i];
					if (f[i]<-220000)
					{
						flag=true;return;
					}
					if (!t[i])
					{
						t[i]=true;
						tail++;q[tail]=i;
					}
				}
			}
		}
		t[q[head]]=false;head++;
	}while(head<=tail);
}

int main()
{
	freopen("jobhunt.in","r",stdin);
	freopen("jobhunt.out","w",stdout);
	scanf("%d%d%d%d%d",&dd,&pp,&cc,&ff,&ss);
	for (i=1;i<=cc;i++)
		for (j=1;j<=cc;j++)
			way[i][j]=oo;
	for (i=1;i<=pp;i++) 
	{
		scanf("%d%d",&x,&y);
		way[x][y]=-dd;
	}
	for (i=1;i<=ff;i++)
	{
		scanf("%d%d%d",&x,&y,&z);
		way[x][y]=min(z-dd,way[x][y]);
	}
	spfa();
	if (flag) printf("-1\n");
	else
	{
		for(i=1;i<=cc;i++) ans=min(ans,f[i]);
		printf("%d\n",-ans);
	}
	return 0;
}