Tyvj P2079(Spfa)

Posted on by
内容目录

P2079 - 防御机制

From tangjz    Normal (OI)
总时限：10s    内存限制：128MB    代码长度限制：64KB

背景 Background

NOIp2012考后欢乐赛第三题

描述 Description

　　服务器的新防御系统快要建好了，但是当正在数据库升级的时候，突然有黑客入侵机房网络，但是就在那时，插网线的房间钥匙丢了。所以Admin开始做防御机房的工作。
　　不过，由于访问某台电脑可经过其他电脑加速，但是不能访问途经电脑，而且单位时间内一台电脑只能发出一条指令，指令不含嵌套指令，Admin只能一台一台的建立防御，幸好如此，黑客也是一台一台入侵，不过二人都会选择最优方案进行操作。所以Admin在主控端(教师端)不停的巡察各台电脑的同时，要求你在简短的时间内帮Admin计算一下哪些电脑将必然被入侵成功，以便于Admin及时做出额外的保护措施，如果所有可能被入侵的电脑都能被保护，那么请计算出将所有连接在主控端上的电脑做好防御所需的总时间。
　　注意：只有黑客的入侵时间短于Admin的防御时间，黑客才能成功入侵。

输入格式 InputFormat

第一行为两个正整数N，M，表示有N台电脑，M条网线。(黑客近似地看为第N台电脑，在机房外)
第二行为N-2个正整数，表示每台电脑的访问时间t。
第三行到第 M+2 行，每行三个整数u,v,w，表示电脑u和v之间有一条网线，使用该网线互相到达对方电脑需要w个单位时间。

输出格式 OutputFormat

输出共两行。
如果有可能会防御失败的电脑，第一行输出"No"，第二行升序输出这些电脑的编号(空格隔开)。
否则第一行输出"Yes"，第二行输出将所有连接在主服务器上的电脑做好防御所需的总时间。

样例输入 SampleInput [复制数据]

[Sample 1]
4 6
1 2
1 2 10
1 3 5
1 4 1
2 3 4
2 4 1
3 4 10

[Sample 2]
5 7
1 1 1
1 2 70
1 3 70
1 4 70
1 5 70
2 5 70
3 5 70
4 5 70

样例输出 SampleOutput [复制数据]

[Sample 1]
No
2

[Sample 2]
Yes
213

数据范围和注释 Hint

样例解释：
第一组：由于1->2:2，4->2:1，所以2号电脑会被入侵成功
第二组：1到2,3,4点的时间均为71,5到2,3,4点的时间均为71，防御成功

对于20% 的数据，1 <=  N  <= 1000 ，1 <=  M  <= 2000
对于60% 的数据，1 <=  N  <= 5000 ，1 <=  M  <= 100000
对于100%的数据，1 <=  N  <= 10000，1 <=  M  <= 200000
对于100%的数据，1 <= t,w <= 10000，1 <= u,v <= N
提示：由于学生贪玩，有可能某个电脑没有连接主机，却接入网络；当然也有部分同学上课被禁网了。

时间限制 TimeLimitation

1s

来源 Source

tjz

这题就是Spfa.


Program defence;
const
   maxn=90000;
   maxm=500000;
   inf=2139062143;
type
   dis_arr=record
              s:longint;
              d:array[1..maxn] of longint;
           end;
var
   n,m,i,j:longint;
   w:array[1..maxn] of longint;
   head,edge,next,weight:array[1..maxm] of longint;
   size:longint;
   d1,d2:dis_arr;
   queue:array[1..6000000] of longint;

Procedure addedge(u,v,w:longint);
begin
   inc(size);
   edge[size]:=v;
   weight[size]:=w;
   next[size]:=head[u];
   head[u]:=size;
end;
Procedure addedge_main;
var
   u,v,w:longint;
begin
   read(u,v,w);
   addedge(u,v,w);addedge(v,u,w);
end;
Procedure spfa(var d:dis_arr);
var
   i,j,now,p:longint;
begin
   i:=1;j:=1;queue[1]:=d.s;
   fillchar(d.d,sizeof(d.d),127);d.d[d.s]:=0;
   while (i<=j) do
   begin
      now:=queue[i];
      p:=head[now];
      while (p<>0) do
      begin
         if (d.d[now]+weight[p]<d.d[edge[p]]) then
         begin
            inc(j);
            queue[j]:=edge[p];
            d.d[edge[p]]:=d.d[now]+weight[p];
         end;
         p:=next[p];
      end;
      inc(i);
   end;
end;
Procedure print;
var
   i,j:longint;
   ans:int64;
   flag:boolean;
begin
   flag:=false;    ans:=0;
   for i:=2 to n-1 do
   begin
      if d1.d[i]<>inf then ans:=ans+int64(w[i]+d1.d[i]);
      if (d1.d[i]>d2.d[i]) then
      begin
         if not(flag) then begin flag:=true; writeln('No'); end
         else write(' ');
         write(i);
      end;
   end;
   if not(flag) then
   begin
      writeln('Yes');
      writeln(ans);
   end
   else writeln;
end;
begin
//   assign(input,'defence.in');
//   reset(input);
   fillchar(head,sizeof(head),0);
   fillchar(edge,sizeof(edge),0);
   fillchar(next,sizeof(next),0);
   size:=0;
   read(n,m); d1.s:=1;d2.s:=n;
   for i:=2 to n-1 do read(w[i]);
   for i:=1 to m do
   begin
      addedge_main;
   end;
   spfa(d1);spfa(d2);
   print;
end.