比赛 20120709 评测结果 AAWWAAWAAAAW
题目名称 聪明的推销员 最终得分 66
用户昵称 fuhao 运行时间 0.563 s
代码语言 Pascal 内存使用 34.56 MiB
提交时间 2012-07-09 11:26:45
显示代码纯文本
  1. const maxn=3001;
  2. var
  3. n,p,x,y,r,i:longint; ans:int64; min:array[-1..maxn] of longint;
  4. w:array[0..maxn,0..maxn] of longint;
  5. u:array[-1..maxn] of boolean;
  6. procedure prim;
  7. var i,j,k:longint;
  8. begin
  9. for i:=-1 to n do min[i]:=maxlongint div 2;
  10. min[0]:=0;
  11. fillchar(u,sizeof(u),#0);
  12. for i:=1 to n+1 do
  13. begin
  14. k:=-1;
  15. for j:=0 to n do
  16. if not u[j] and (min[j]<min[k]) then k:=j;
  17. if k=-1 then break;
  18. u[k]:=true;
  19. for j:=0 to n do
  20. if not u[j] and (min[j]>w[k,j]) then min[j]:=w[k,j];
  21. end;
  22. ans:=0;
  23. for i:=0 to n do
  24. begin
  25. if (min[i]=w[0,0]) or (min[i]=maxlongint div 2) then
  26. begin writeln('NO'); writeln(i);
  27. close(input); close(output); halt;
  28. end;
  29. ans:=ans+min[i];
  30. end;
  31. end;
  32. begin
  33. assign(input,'salenet.in'); reset(input);
  34. assign(output,'salenet.out'); rewrite(output);
  35. fillchar(w,sizeof(w),$7f div 2);
  36. readln(n);
  37. readln(p);
  38. for i:=1 to p do
  39. begin
  40. readln(x,y);
  41. if w[0,x]>y then w[0,x]:=y;
  42. end;
  43. readln(r);
  44. for i:=1 to r do
  45. begin
  46. readln(x,y);
  47. w[x,y]:=0;
  48. end;
  49. prim;
  50. writeln('YES');
  51. writeln(ans);
  52. close(input); close(output);
  53. end.