The method comes from this big guy
LuoGu Title gate
[Abstract]
There is a very ingenious way to solve this problem: layered graph + SPFA
It can be seen from the question meaning that the output answer is only related to the buying and selling price, and the buying and selling are limited to one time
It's very difficult for us to maintain the status of buying and selling if it's general broad search, and it's also difficult to update the answer

This method is very convenient
Let's build a three-tier diagram

1. First floor: initial road, can walk around without weight
2. Layer 2: you can walk up and down the same floor as the first floor, but it comes from the first floor. A road is built from the first floor to the second floor, indicating purchase. The weight is - price
3. Layer 3: you can walk up and down the same layer as the first layer, but it comes from the second layer. A road is built from the second layer to the third layer, which means selling. The weight is the price

And the end point is n in the third layer. The final result can be compared with 0
This method has a small code size and is very beautiful

Code:

```uses math;
var
vis:array[0..1000000] of boolean;
n,m,x,y,z,i,h,tail,e,ans,num:longint;

begin
inc(num);
u[num]:=y;
dist[num]:=z;
end;

begin
for i:=1 to n do read(w[i]);
for i:=1 to m do
begin
if z=2 then
begin
end;
end;
q[1]:=1;
tail:=1;
for i:=2 to 3*n do dis[i]:=-maxlongint;
while h<tail do
begin
inc(h);
x:=q[h];
vis[x]:=false;
while i>0 do
begin
e:=u[i];
if (dis[e]<dis[x]+dist[i]) then
begin
dis[e]:=dis[x]+dist[i];
if not vis[e] then
begin
inc(tail);
q[tail]:=e;
vis[e]:=true;
end;
if e=3*n then ans:=max(ans,dis[e]);
end;
i:=next[i];
end;
end;
writeln(ans);
end.
```

Posted on Mon, 06 Jan 2020 20:05:25 -0800 by philhale