首先机器人是并行的;
很容易想到到某个点的最短用时
=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.