比赛 20120709 评测结果 AAWWAAWAAAAW
题目名称 聪明的推销员 最终得分 66
用户昵称 fuhao 运行时间 0.563 s
代码语言 Pascal 内存使用 34.56 MiB
提交时间 2012-07-09 11:26:45
显示代码纯文本
const maxn=3001;
var
 n,p,x,y,r,i:longint; ans:int64; min:array[-1..maxn] of longint;
 w:array[0..maxn,0..maxn] of longint;
 u:array[-1..maxn] of boolean;
 procedure prim;
 var i,j,k:longint;
 begin
  for i:=-1 to n do min[i]:=maxlongint div 2;
  min[0]:=0;
  fillchar(u,sizeof(u),#0);
  for i:=1 to n+1 do
   begin
    k:=-1;
    for j:=0 to n do
     if not u[j] and (min[j]<min[k]) then k:=j;
    if k=-1 then break;
    u[k]:=true;
    for j:=0 to n do
     if not u[j] and (min[j]>w[k,j]) then min[j]:=w[k,j];
   end;
  ans:=0;
  for i:=0 to n do
   begin
    if (min[i]=w[0,0]) or (min[i]=maxlongint div 2) then
     begin writeln('NO'); writeln(i);
           close(input); close(output); halt;
     end;
    ans:=ans+min[i];
   end;
 end;
begin
 assign(input,'salenet.in'); reset(input);
 assign(output,'salenet.out'); rewrite(output);
 fillchar(w,sizeof(w),$7f div 2);
 readln(n);
 readln(p);
 for i:=1 to p do
  begin
   readln(x,y);
   if w[0,x]>y then w[0,x]:=y;
  end;
 readln(r);
 for i:=1 to r do
  begin
   readln(x,y);
   w[x,y]:=0;
  end;
 prim;
 writeln('YES');
 writeln(ans);
 close(input); close(output);
end.