记录编号	32825	评测结果	AAAAAAAATTW
题目名称	[USACO Nov09] 找工作	最终得分	72
用户昵称	Des.	是否通过	未通过
代码语言	Pascal	运行时间	3.206 s
提交时间	2011-11-08 16:31:56	内存使用	0.69 MiB

program jobhunt;
var a:array[1..220,1..220]of longint;
    b:array[1..220]of boolean;
    f,d:array[1..220]of int64;
    t,k,m,n,i,j,s0,p,st,x,z:longint;
    q:array[1..100000]of longint;
procedure search(i,s:longint);
var t,k,j:longint;
begin
if (b[i])then
  begin
    if s-d[i]>0 then
      begin
        writeln(-1);
        close(output);
        halt;
      end;
    exit;
  end;
b[i]:=true;
for j:=1 to n do
  if (a[i,j]>=0) then
    begin
      d[j]:=s;
      search(j,s+s0-a[i,j]);
    end;
b[i]:=false;
end;
begin
assign(input,'jobhunt.in');
reset(input);
assign(output,'jobhunt.out');
rewrite(output);
readln(s0,m,n,p,st);
for t:=1 to n do
  for k:=1 to n do
    a[t,k]:=-1;
for t:=1 to m do
  begin
    readln(i,j);
    a[i,j]:=0;
  end;
for t:=1 to p do
  begin
    readln(i,j,k);
    a[i,j]:=k;
  end;
fillchar(b,sizeof(b),false);
search(st,0);
i:=0;
j:=1;
q[1]:=st;
fillchar(b,sizeof(b),false);
b[st]:=true;
for t:=1 to n do
  f[t]:=-maxlongint;
f[st]:=s0;
repeat
  inc(i);
  x:=q[i];
  for k:=1 to n do
    if (a[x,k]>=0)and(f[k]<f[x]+s0-a[x,k]) then
      begin
        f[k]:=f[x]+s0-a[x,k];
        if b[k]=false then
          begin
            inc(j);
            q[j]:=k;
            b[k]:=true;
          end;
      end;
  b[x]:=false;
until i=j;
i:=0;
for t:=1 to n do
  if f[t]>i then i:=f[t];
writeln(i);
close(output);
end.