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

#include <iostream>
#include <fstream>

using namespace std;

int d,p,c,ff,s;
int a[300][300];
int i,j,k,l;
int f[300],q[1000000];
int head,tail;

int main()
{
	ifstream fin("jobhunt.in");
	ofstream fout("jobhunt.out");
	
	fin>>d>>p>>c>>ff>>s;
	for (i=1;i<=p;i++)
	{
		fin>>j>>k;
		a[j][k]=-d;
	}
	for (i=1;i<=ff;i++)
	{
		fin>>j>>k>>l;
		a[j][k]=l-d;
	}
	
	for (i=1;i<=c;i++)
		f[i]=9999999;
	
	q[1]=s;
	f[s]=-d;
	head=1;
	tail=1;
	while (head<=tail)
	{
		for (i=1;i<=c;i++)
			if (a[q[head]][i]!=0)
				if ((f[q[head]]+a[q[head]][i])<f[i])
				{
					f[i]=(f[q[head]]+a[q[head]][i]);
					if (f[i]<(-c*d))
					{
						fout<<"-1";
						fin.close();
						fout.close();
						return 0;
					}
					tail++;
					q[tail]=i;
				}
		head++;
	}
	
	l=99999;
	for (i=1;i<=c;i++)
		if (f[i]<l)
			l=f[i];
	l=-l;
	
	fout<<l;
	fin.close();
	fout.close();
	
	return 0;
}