记录编号	27423	评测结果	AAAAAAAAAAA
题目名称	[USACO Nov09] 找工作	最终得分	100
用户昵称	Citron酱	是否通过	通过
代码语言	C++	运行时间	0.006 s
提交时间	2011-09-22 11:46:57	内存使用	0.27 MiB

#include <fstream>
#include <climits>

#define I_F "jobhunt.in"
#define O_F "jobhunt.out"

const int MAXn=220;

struct dllb
{
	int x;
	dllb *next;
};

struct lb
{
	int x, s;
	lb *next;
}*map[MAXn]={NULL};

int n,s,d;
int ans;

void Input();
void Spfa();
void Output();

int main()
{
	Input();
	Spfa();
	Output();
	return 0;
}

void Input()
{
	int p,f,x,y,t;
	lb *temp;
	std::ifstream fin(I_F);
	fin>>d>>p>>n>>f>>s;
	s--;
	for (int i=0; i<p; i++)
	{
		fin>>x>>y;
		x--, y--;
		temp=map[x];
		map[x]=new lb;
		map[x]->x=y;
		map[x]->s=-d;
		map[x]->next=temp;
	}
	for (int i=0; i<f; i++)
	{
		fin>>x>>y>>t;
		x--, y--;
		for (temp=map[x]; temp!=NULL; temp=temp->next)
			if (temp->x==y)
				break;
		if (temp==NULL)
		{
			temp=map[x];
			map[x]=new lb;
			map[x]->x=y;
			map[x]->s=t-d;
			map[x]->next=temp;
		}
	}
	fin.close();
}

void Spfa()
{
	int count[MAXn]={0};
	count[s]=1;
	int minl[MAXn];
	for (int i=0; i<n; minl[i++]=INT_MAX);
	minl[s]=0;
	dllb *pt[MAXn]={NULL};
	dllb *head=new dllb;
	dllb *tail=head, *temp;
	head->x=s;
	head->next=NULL;
	pt[s]=head;
	while (head!=NULL)
	{
		for (lb *i=map[head->x]; i!=NULL; i=i->next)
			if (i->s+minl[head->x]<minl[i->x])
			{
				if ((++count[i->x])>n)
				{
					ans=-1;
					return;
				}
				minl[i->x]=i->s+minl[head->x];
				if (pt[i->x]==NULL)
				{
					tail->next=new dllb;
					tail=tail->next;
					tail->x=i->x;
					tail->next=NULL;
					pt[i->x]=tail;
				}
			}
		pt[head->x]=NULL;
		temp=head;
		head=head->next;
		delete temp;
	}
	
	ans=INT_MAX;
	for (int i=0; i<n; i++)
		ans=(ans<minl[i])?ans:minl[i];
	ans=d-ans;
}

void Output()
{
	std::ofstream fout(O_F);
	fout<<ans<<std::endl;
	fout.close();
}