这是一道描述非常不清楚的题目
首先解释一下,题目中的ti是任务开始时间不是结束时间,
然后维修人员可以理解为可以再任意时间从公司出发;
好,首先不难想到用floyd预处理一下;
然后我们把每个任务看成一个点,显然有些维修员完成一个任务后还可以接着完成别的任务;
这样我们就可以构造出一张有向无环图;
考虑到每个任务这需要我们做一次且仅一次,并且现在我们要求最少的人去覆盖所有的点;
不难想到最小路径覆盖,构造二分图求解即可
const inf=;
type node=record
next,point:longint;
end; var edge:array[..] of node;
p,cx,cy,d,s,w:array[..] of longint;
v:array[..] of boolean;
a:array[..,..] of longint;
len,ans,i,j,n,m,k:longint; function min(a,b:longint):longint;
begin
if a>b then exit(b) else exit(a);
end; procedure add(x,y:longint);
begin
inc(len);
edge[len].point:=y;
edge[len].next:=p[x];
p[x]:=len;
end; function find(x:longint):longint;
var i,y:longint;
begin
i:=p[x];
while i<>- do
begin
y:=edge[i].point;
if not v[y] then
begin
v[y]:=true;
if (cy[y]=-) or (find(cy[y])=) then
begin
cx[x]:=y;
cy[y]:=x;
exit();
end;
end;
i:=edge[i].next;
end;
exit();
end; begin
readln(n,m);
while (n<>) do
begin
len:=;
fillchar(p,sizeof(p),);
for i:= to n do
for j:= to n do
begin
read(a[i,j]);
if a[i,j]=- then a[i,j]:=inf;
end;
for k:= to n do
for i:= to n do
if (i<>k) then
for j:= to n do
if (i<>j) and (j<>k) then
a[i,j]:=min(a[i,j],a[i,k]+a[k,j]);
for i:= to m do
readln(w[i],s[i],d[i]);
for i:= to m do
for j:= to m do
begin
if i=j then continue;
if a[w[i],w[j]]+s[i]+d[i]<=s[j] then add(i,j);
end;
ans:=;
fillchar(cx,sizeof(cx),);
fillchar(cy,sizeof(cy),);
for i:= to m do
if cx[i]=- then
begin
fillchar(v,sizeof(v),false);
ans:=ans+find(i);
end;
writeln(m-ans);
readln(n,m);
end;
end.