题解 P1073 【最优贸易】

蹦极僵尸 · 2014-04-07 18:42:09 · 题解

题意：从1到n的路径中，找出一个最小的水晶球买入价格，再找出一个最大的买入价格，也就是说使得差价最大，赚取的旅费最多，最后回到n点。

本题可以用SPFA来做，用两个数组f和g数组分别来记录到i点的最大赚取的旅费和到i的最小买入价格，那么f[y]:=min(f[x] , f[y] , a[y]-g[x]) 可以是从y点卖从到x的路径中最小的那个买入价格买入，或者就是x的最大差价。 g[x]:=min(a[y] , g[x])

var tot,n,m,x,y,d,i,j,t,head,tail:longint;
    que,a,first,g,f,next,y1:array[0..101001] of longint;
    b:array[0..100100] of boolean;
begin
  read(n,m);
  fillchar(first,sizeof(first),0);
  fillchar(f,sizeof(f),200);
  for i:=1 to n do begin read(a[i]);g[i]:=a[i];end;
  for i:=1 to m do begin
    read(x,y,d);
    inc(tot);
    y1[tot]:=y;
    next[tot]:=first[x];
    first[x]:=tot;
    if d=2 then begin
      inc(tot);
      y1[tot]:=x;
      next[tot]:=first[y];
      first[y]:=tot;
    end;
  end;
  head:=1;tail:=1;b[1]:=true;que[1]:=1;f[1]:=0;
  while head<=tail do begin
    x:=que[head mod 100000];
    t:=first[x];
    while t>0 do begin
      y:=y1[t];
      if (f[x]>f[y])or(g[x]<g[y])or(a[y]-g[x]>f[y]) then begin
        if f[x]>f[y] then f[y]:=f[x];
        if a[y]-g[x]>f[y] then f[y]:=a[y]-g[x];
        if g[x]<g[y] then g[y]:=g[x];
        if b[y]=false then begin
          b[y]:=true;inc(tail);
          que[tail mod 100000]:=y;
        end;
      end;
      t:=next[t];
    end;
    inc(head);
    b[x]:=false;
  end;
  if f[n]=f[0] then writeln(0) else writeln(f[n]);
end.