题解 P1073 【最优贸易】

· · 题解

我刚开始想得偏简单了，我的想法是：按每个点向其他点进行扩展，扩到就入队，入队就记录前驱，最后把每条路实践一遍。然而事实证明，挂了。

同其他几位大神说的，此题可用两次spfa解决，然而这对最短路渣渣的我来说无疑是一次挑战（本人鶸，大神勿喷），第一次，从1开始走，走到终点，求出min[i]，即从1到i的最小进价，然后如法炮制地从n走回来，求出max[i]，即从i到n的最大出售价，这个其他几位大神也提到了（然而我居然实现了将近3个小时！！！）。那么，剩下的我在代码里会进行批注


var
  i,j,n,m,x,y,z,num,maxn,num2:longint;
  a,max,min:array[0..100001] of integer;
  que,head,head2:array[0..100001] of longint;
  inque:array[0..100001] of boolean;
  vet,next,vet2,next2:array[0..500001] of longint;
procedure add(x,y:longint);
begin
  inc(num);
  next[num]:=head[x];
  head[x]:=num;
  vet[num]:=y;
end;
procedure add2(x,y:longint);//从n回来的边，从终点走回来是逆向思维，所以路线要相反（这样写的话其实本质就是从i走到n，只是为了spfa是单源最短路而倒过来）
begin
  inc(num2);
  next2[num2]:=head2[x];
  head2[x]:=num2;
  vet2[num2]:=y;
end;
procedure spfamin;//1到i的最小进价
var h,t,u,v,e:longint;
begin
  fillchar(inque,sizeof(inque),false);
  h:=1;t:=1;que[1]:=1;inque[1]:=true;
  while h<=t do
    begin
      u:=que[(h-1) mod n+1];
      inc(h);e:=head[u];
      inque[u]:=false;
      while e<>-1 do
        begin
          v:=vet[e];
          if min[v]>min[u] then
            begin
              min[v]:=min[u];
              if not inque[v] then
                begin
                  inc(t);
                  que[(t-1) mod n+1]:=v;
                  inque[v]:=true;
                end;
            end;
          if min[v]>a[v] then//保证每个搜到的点都至少进一次队列
            begin
              min[v]:=a[v];
              if not inque[v] then
                begin
                  inc(t);
                  que[(t-1) mod n+1]:=v;
                  inque[v]:=true;
                end;
            end;
          e:=next[e];
        end;
    end;
end;
procedure spfamax;//i到n（n到i）的最大出售价
var h,t,u,v,e:longint;
begin
  fillchar(inque,sizeof(inque),false);
  h:=1;t:=1;que[1]:=n;inque[n]:=true;
  while h<=t do
    begin
      u:=que[(h-1) mod n+1];
      inc(h);e:=head2[u];
      inque[u]:=false;
      while e<>-1 do
        begin
          v:=vet2[e];
          if max[v]<max[u] then
            begin
              max[v]:=max[u];
              if not inque[v] then
                begin
                  inc(t);
                  que[(t-1) mod n+1]:=v;
                  inque[v]:=true;
                end;
            end;
          if max[v]<a[v] then//保证每个搜到的点都至少进一次队列
            begin
              max[v]:=a[v];
              if not inque[v] then
                begin
                  inc(t);
                  que[(t-1) mod n+1]:=v;
                  inque[v]:=true;
                end;
            end;
          e:=next2[e];
        end;
    end;
end;
begin
  read(n,m);
  for i:=1 to n do begin read(a[i]);head[i]:=-1;head2[i]:=-1;min[i]:=10000;max[i]:=0;end;
  num:=0;num2:=0;
  for i:=1 to m do
    begin
      read(x,y,z);
      if z=2 then begin add(x,y);add(y,x);add2(x,y);add2(y,x);end 
             else begin add(x,y);add2(y,x);end;//注意这里！从终点往回建边的逆向思维实现方法！很容易搞错！
    end;
  spfamin;spfamax;
  maxn:=0;
  for i:=1 to n do
    if maxn<max[i]-min[i] then maxn:=max[i]-min[i];//求出每个点的差价，算出最大值
  write(maxn);//因为初始化是0所以如果都不合算那么也不会赋值
end.