bzoj1922

时间:2023-03-08 19:49:24

首先机器人是并行的;

很容易想到到某个点的最短用时

=max(到这个点的最短路,max(到保护这个点结界所在点的最短用时))

所以我们在做dij的时候,d[j]维护最短路,w[j]维护所有保护这个点结界所在的点的最短用时的最大值

在做最短路松弛的时候,我们肯定是要加一个优先条件即这个点没有结界保护了

注意会爆longint;

 const inf=;
var a:array[..,..] of longint;
    b:array[..,..] of boolean;
    w,d:array[..] of int64;
    v:array[..] of boolean;
    s:array[..] of longint;
    k,n,m,i,j,x,y:longint;
    z,p,mid:int64; function min(a,b:int64):int64;
  begin
    if a>b then exit(b) else exit(a);
  end; function max(a,b:int64):int64;
  begin
    if a>b then exit(a) else exit(b);
  end; begin
  readln(n,m);
  for i:= to n do
    for j:= to n do
      if i<>j then a[i,j]:=;
  for i:= to m do
  begin
    readln(x,y,z);
    a[x,y]:=min(a[x,y],z);
  end;
  for i:= to n do
  begin
    read(s[i]);
    for j:= to s[i] do
    begin
      read(x);
      b[i,x]:=true;
    end;
  end;
  d[]:=;
  for i:= to n do
    d[i]:=inf;
  for i:= to n- do
  begin
    mid:=inf;
    k:=;
    for j:= to n do
    begin
      z:=max(d[j],w[j]);
      if not v[j] and (s[j]=) and (mid>z) then
      begin
        mid:=z;
        k:=j;
      end;
    end;
    if k= then break;
    v[k]:=true;
    for j:= to n do
      if not v[j] then
      begin
        if b[j,k] then
        begin
          dec(s[j]);
          w[j]:=max(w[j],mid);
        end;
        d[j]:=min(d[j],mid+a[k,j]);
      end;
  end;
  writeln(max(d[n],w[n]));
end.