Luogu p1073 [noip2009 improvement group] optimal trade (layered diagram + shortest path)

Luogu P1073 [NOIP2009 Improvement group ] The best trade （ Hierarchical graph + shortest path ）

The question ：

Digraph with point weight , The point weight of each point represents , The price at which the crystal ball is purchased or sold . Seek from 1 To n, Choose to buy crystal balls at one point , Then choose the maximum profit after selling the crystal ball at one point . A point can pass many times .

Ideas ：

Method 1 ： Shrinkage point +dp（ A topological sort ）

Method 2 ： Hierarchical graph + shortest path ：

picture source

The edge weight of each layer is 0, The weights connecting the points of the first layer to the points of the second layer are negative numbers of point weights , Means to buy at this point , The weight of the points connecting the second layer to the third layer is a positive number of the point weight , Means sell at this point

Because you have negative power , Can only run spfa