比赛 20120709 评测结果 WAWWAAWWWAAW
题目名称 聪明的推销员 最终得分 41
用户昵称 wo shi 刘畅 运行时间 0.053 s
代码语言 Pascal 内存使用 44.06 MiB
提交时间 2012-07-09 10:52:59
显示代码纯文本
var
  n,p,m,i,x,y,ans:longint;
  time,ru:array[0..1000000]of longint;
  v,b:array[0..1000000]of boolean;
  g:array[0..3000,0..3000]of longint;

function yes:boolean;
var
  i:longint;
begin
  for i:=1 to n do
  if (ru[i]=0)and(not v[i]) then exit(false);
  exit(true);
end;

procedure go(k:longint);
var
  i,j:longint;
begin
  b[k]:=true;
  for i:=1 to g[k,0] do
  begin
    j:=g[k,i];
    if not b[j] then go(j);
  end;
end;

begin
  assign(input,'salenet.in'); reset(input);
  assign(output,'salenet.out'); rewrite(output);
  readln(n);
  readln(p);
  for i:=1 to p do
  begin
    readln(x,time[x]);
    v[x]:=true;
  end;
  readln(m);
  for i:=1 to m do
  begin
    readln(x,y);
    inc(g[x,0]);
    g[x,g[x,0]]:=y;
    inc(ru[y]);
  end;
  if yes then
  begin
    ans:=0;
    for i:=1 to n do
    if v[i] then inc(ans,time[i]);
    writeln('YES');
    writeln(ans);
  end
  else begin
    for i:=1 to n do
    if v[i] then go(i);
    writeln('NO');
    for i:=1 to n do
    if not b[i] then
    begin
      writeln(i);
      break;
    end;
  end;
  close(input);
  close(output);
end.