记录编号	35145	评测结果	AAAAAAAAAAA
题目名称	[USACO Nov09] 找工作	最终得分	100
用户昵称	kaaala	是否通过	通过
代码语言	C++	运行时间	0.005 s
提交时间	2012-02-16 10:58:41	内存使用	0.27 MiB

#include<iostream>
#include<cstdio>
#include<cstring>
#include<cstdlib>
#include<cmath>
#include<algorithm>
#include<deque>

using namespace std;

const int oo=~0u>>2;

struct Node
{
	int t,cost;
	Node *next;
	Node(int _t,int _cost,Node *_next):t(_t),cost(_cost),next(_next){}
}*Map[230];

int D,P,C,F,S,ans=oo;

void addedge(int s,int t,int cost)
{
	Map[s]=new Node(t,cost,Map[s]);
}

void spfa()
{
	deque<int>deq;
	bool vis[230];
	int dist[230],tm[230];
	for(int i=1;i<=C;i++)
	{
		dist[i]=oo;
		vis[i]=false;
		tm[i]=0;
	}
	deq.push_back(S);
	dist[S]=-D;
	while(!deq.empty())
	{
		int u=deq.front();
		deq.pop_front();
		vis[u]=false;
		for(Node *p=Map[u];p;p=p->next)
		{
			int t=p->t,cost=p->cost;
			if(dist[t]>dist[u]+cost)
			{
				dist[t]=dist[u]+cost;
				if(!vis[t])
				{
					tm[t]++;
					vis[t]=true;
					if(dist[t]<dist[u])
						deq.push_front(t);
					else
						deq.push_back(t);
					if(tm[t]>C)
					{
						ans=-1;
						return;
					}
				}
			}
		}
	}
	for(int i=1;i<=C;i++)
		ans=min(ans,dist[i]);
	return;
}

int main()
{
	freopen("jobhunt.in","r",stdin);
	freopen("jobhunt.out","w",stdout);
	scanf("%d%d%d%d%d",&D,&P,&C,&F,&S);
	for(int i=1;i<=P;i++)
	{
		int a,b;
		scanf("%d%d",&a,&b);
		addedge(a,b,-D);
	}
	for(int i=1;i<=F;i++)
	{
		int a,b,c;
		scanf("%d%d%d",&a,&b,&c);
		addedge(a,b,c-D);
	}
	spfa();
	printf("%d\n",-ans);
	return 0;
}